Talk:Sieve of Atkin

Comments

I'm hoping that someone, if I don't have time to do it, will fill in details like how the sieve determines how many values for x and y fulfill the deletion question. If we can move the article more toward the easy reading of Sieve of Eratosthenes, that would be great. — 131.230.133.185 5 July 2005 19:26 (UTC)

I concure!

I agree. I would help if I understood the algorithm. Now it's off to somewhere else for a better explanation. — Preceding unsigned comment added by 176.42.70.2 (talk) 17:35, 26 November 2012 (UTC)

Class One, Class Two, Class Three

I just did some rewording on the algorithm. However, I do not know exactly about the algorithm, and am confused by the following:

Then, for each remaining number, n:

In class one, count the number of combinations of x > 0 and y > 0 that are solutions to 4x2 + y2 = n.

In class two, count the number of combinations of x > 0 and y > 0 that are solutions to 3x2 + y2 = n.

In class three, count the number of combinations of x > 0, y > 0, and x>y that are solutions to 3x2 - y2 = n.

If the count was even, delete the number from the list.

What are classes? The article says "If the count was even". If what count was even (any one of them or the sum of them)? Clarification would make the article easier to read and understand. --mets501 04:12, 4 March 2006 (UTC)

I think the "classes" are the backup lists (i.e., the ones that hold values that are not yet determined to be prime) that were just mentioned previously. I'm not sure enough about this to edit the page myself, however, as I'm not familiar with the Sieve of Atkin. In regards to the count being even, it refers to the number of combinations for each listed "class". If the number of combinations (say for class 1, of 4x^2 + y^2 = n) is even for the current n, then you get rid of the number. Any word from an expert on this would be great, however. Opblaaskrokodil 03:27, 26 March 2006 (UTC)

I would like to know if the ordere pair solutions have to be integers. For example, the non prime number 91 would be in list 2. I can find only one ordered integer pair (3, 8) to solve 3x^2 + y^2 = 91. Thus I do not remove it from the list, and it would erroneously go into the list of primes. —the preceding comment is by 24.66.94.140 - 16:55, 15 April 2006 (UTC): Please sign your posts!

The solutions certainly have to be integers, otherwise there would be an infinite number of solutions for every number. As for 91, you missed (5, 4). -- EJ 22:06, 4 May 2006 (UTC)

Clean up tag removed

I removed the clean up tag because I couldn't figure out why it was put on in the first place. Anyone who wants to put the tag back on had better explain not only why but also why they couldn't fix what they thought was wrong with the page themselves in the first place. Anton Mravcek 20:48, 8 May 2006 (UTC)

I'm not sure why a cleanup tag was justified either (unless because the explanation of the algorithm leaves a bit to be desired). I did add an expandsect tag to the "proof and explanations" section; there is currently no explanation of why the business with calculating the various numbers of combinations of x and y actually helps weed out non-primes. Maybe it would be obvious to a mathematician why this is so, but it sure isn't obvious to me. In fact, I have no idea (if I did, I'd add the extra explanation myself). Zoicon5 18:06, 26 May 2006 (UTC)

I went and looked up the original paper using the external link; this was clear enough for me to be able to add further explanation of the part I hadn't understood before, so I did that (and removed the "expandsect" tag). Zoicon5 19:13, 26 May 2006 (UTC)

I've cleaned up the article quite a bit, making it simpler and easier to follow (like the Sieve of Eratosthenes article) and showing where to obtain proofs of the various assertions. I've removed quasi-optimizations in favor of understandability (the reader can choose his own optimizations or copy the C code linked at the bottom). — 131.230.133.186 18:53, 28 May 2006 (UTC)

Confused about x and y

I'm confused about the X and Y variables appearing out of nowhere in the psuedo code? I don't know enough maths to follow well, i'm using this to implement a python script that will do this, basically. I presume the X and Y should be I and J (from the for....do... loops?) someone with more math/algorithm nous?

Well, the previous pseudocode declared x and y, but someone declared it "crud" and "wrong"; it looked like this:

HighestFactor = 1000000;               // Enough. A prime would be better.
Limit = HighestFactor^2;               // Resultant search span.
array is_prime[5:Limit] initial false; // Sieve array.
biginteger x,y,n,k;                    // Must be able to hold 5*Limit: 4x^2 + y^2!
// put in candidate primes: integers which have an odd number of representations by certain quadratic forms.
for x:=1:HighestFactor do
 for y:=1:HighestFactor do
   n:=4*x^2 + y^2; if n <= Limit and n mod 12 = 1 or = 5 then     is_prime[n]:=not is_prime[n];
   n:=3*x^2 + y^2; if n <= Limit and n mod 12 = 7 then            is_prime[n]:=not is_prime[n];
   n:=3*x^2 - y^2; if n <= Limit and x > y and n mod 12 = 11 then is_prime[n]:=not is_prime[n];
 next y;
next x;
// eliminate composites by sieving
// if n is prime, omit all multiples of its square; this is sufficient because 
// composites which managed to get on the list cannot be square-free
for n:=5:HighestFactor do
  if is_prime[n] then for k:=n^2:Limit:n^2 do is_prime[k]:=false; next k;
next n;
// Present the results.
print 2, 3; for n:= 5:Limit do if is_prime[n] then print n; next n;

And notice that the variables do not appear "out of nowhere" as you complained. As for the "wrongness", I transliterated it into Pascal, producing

Program PrimesByAtkin; uses DOS, crt;
 const HighestFactor = 100;             {Enough. A prime would be better.}
 const Limit = HighestFactor*HighestFactor;             {Resultant search span.}
 var is_prime: array[5..Limit] of boolean;              {Sieve array.}
 var x,y,n,k: longint;                  {Must be able to hold 5*Limit: 4x^2 + y^2!}
 var outa: text; {Bizarre declaration of an output file.}
 BEGIN
  for n:=5 to Limit do is_prime[n]:=false;
 {Put in candidate primes: integers which have an odd number of representations by certain quadratic forms.}
  for x:=1 to HighestFactor do
   for y:=1 to HighestFactor do
    begin
     n:=4*x*x + y*y; if (n <= Limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then is_prime[n]:=not is_prime[n];
     n:=3*x*x + y*y; if (n <= Limit) and (n mod 12 = 7) then                     is_prime[n]:=not is_prime[n];
     n:=3*x*x - y*y; if (n <= Limit) and (x > y) and (n mod 12 = 11) then        is_prime[n]:=not is_prime[n];
    end; {next y;}
  {next x;}
 { eliminate composites by sieving
 if n is prime, omit all multiples of its square; this is sufficient because
 composites which managed to get on the list cannot be square-free}
  for n:=5 to HighestFactor do
   if is_prime[n] then
    begin
     {for k:=n^2:Limit:n^2 do is_prime[k]:=false; next k;}
     k:=n*n;
     repeat
      is_prime[k]:=false;
      k:=k + n*n;
     until k > Limit;
    end;
 {next n;}
 {Present the results.}
  assign(outa,'PrimesA.txt'); rewrite(outa);
  writeln(outa,2);writeln(outa,3); for n:= 5 to Limit do if is_prime[n] then writeln(outa,n); {next n;}
  close(outa);
 END.

Which is not pseudocode but actual Pascal source, which compiles and works. You should have no trouble converting into python, or anything else. Incidentally, There is no need to try "if x == true then" in a C-gibberish form, "if x then" should do.

NickyMcLean 20:10, 29 November 2006 (UTC)

How is this

Perhaps the following pseudocode example would be more suiting to you McLean. I apologize for my previous mistakes in not changing x and y to i and j respectively.

Please note that in your example:

if is_prime[n] then for k:=n^2:Limit:n^2 do

is very much gibberish

limit = 1000000                         // Resultant search span. ^ being the exponentiation operation
highest_factor = sqrt(limit)            // Square root of the search span
is_prime[limit]                         // Sieve array. Initialize all entries to the equivalent of a false boolean
(n, i, j) = (0, 0, 0)                   // Must be able to hold 5*Limit!

// Put in candidate primes: Integers which have an odd number of representations by certain quadratic forms.

for i from 1 to highest_factor do
    for j from 1 to highest_factor do
       n = 4*i^2 + j^2
       if n <= limit and ((n mod 12 == 1) or (n mod 12 == 5))  then
           is_prime[n] = not is_prime[n]
       end if

       n = 3*i^2 + j^2
       if n <= limit and (n mod 12 == 7) then
           is_prime[n] = not is_prime[n]
       end if

       n = 3*i^2 - j^2
       if n <= limit and (i > j) and (n mod 12 == 11) then
           is_prime[n] = not is_prime[n]
       end if
    end for
end for

// Eliminate composites by sieving
// If n is prime, omit all multiples of its square; this is sufficient because
// composites which managed to get on the list cannot be square-free

for i from 5 to highest_factor do
    if is_prime[i] == true then
       for j from i^2 to limit step i^2 do
           is_prime[j] = false
       end for
    end if
end for

// With the exception of 2 and 3, is_prime now contains boolean values
// for the primality of integers from 5 to limit at their respective indexes in the array

Here is a Python example, so you can see how easily my pseudocode translates into the language:

    import math
 
    limit = 100
    highest_factor = int(math.floor(math.sqrt(limit)))
    is_prime = [False] * limit
    # i, j and n will be dynamically created
 
    for i in xrange(1, highest_factor):
        for j in xrange(1, highest_factor):
            n = 4*i**2+j**2
            if n <= limit and ((n % 12 == 1) or (n % 12 == 5)):
                is_prime[n] = not is_prime[n]
            
            n = 3*i**2+j**2
            if n <= limit and (n % 12 == 7):
                is_prime[n] = not is_prime[n]
                
            n = 3*i**2 - j**2
            if n <= limit and (i > j) and (n % 12 == 11):
                is_prime[n] = not is_prime[n]
                
    for i in xrange(5, highest_factor):
        if is_prime[i]:
            for j in xrange(i**2, limit, i**2):
                is_prime[j] = False
 
    # Print the integers
    for i in xrange(5, limit):
        if is_prime[i]:
            print i

No, I was not the person who declared it 'wrong' or whatever, I was in fact, the person who removed that comment. I just think my pseudocode is cleaner and easier to understand. I do not mean it as an insult to you.

65.33.145.252 03:52, 30 November 2006 (UTC)

(I wasn't accusing you: the other person merely has some other IP address recorded. I was peeved by the crass remark, but against the possibility of a miscode, the Pascal transliteration offered some support though the many minor changes could introduce error)

Ah, I see now that Python is indeed one of the languages that uses indentation rather than do ... end, begin ... end or {...} (which in Pascal means a comment) - I'd half-remembered that. However I'd suggest as for layout, having the three action lines one above the other facilitates comparison and the separation of the conditions from the boringly simple actions (whose expression requires many symbols just to flip a bit) which are each the same. There are some (very obscure) languages that do use a 2-dimensional layout, but they're a different world. As a general point, depending on layout is risky because many times your carefully-indented text will be simplified to flush-left by over-helpful web page handlers. Thus it can help to signify the scope of blocks by explicit markers, which is also a hint to those unfamiliar with the notion that a visual hint (layout) does in this case translate to a formal specification of block scope.

I agree that for i:=start:stop:step do is obscure, but for i:=start:stop is common (the idea has reached Matlab, for example) and reasonably similar to a common form of array bound specification. Pascal's Array[start..stop] is particularly lame. So yes, I should have explained that, or used the form with keywords, as in your Pythonish version. I'd suggest though that the Pythonish "with" keyword is unfortunate, and could better be replaced by "step" for pseudocode, even if in Python it has some special other meaning. Ah, I see that in actual Python, a peculiar form is used, without hints. I think that the syntax for i:=start:stop:step do ... next i; (with the :step optional) is completely satisfactory, and if I ruled the world... NickyMcLean 19:50, 30 November 2006 (UTC)

Perhaps then we can work together on the pseudocode, to generate a clean and readable format using both our styles that is not only satisfactory to us both, but much easier for those trying to translate it into their preferred language and either of our examples would've been on their own. I'm more than happy to compromise 'with' for 'step' or 'next'. I look forward to your thoughts.

65.33.145.252 21:58, 30 November 2006 (UTC)

Well, I'd allow for i from n^2 to Limit step n^2 do instead of for i:=n^2:Limit:n^2 do in the spirit of easy readability for those not familiar with the form, but introducing the "cup" and "cap" symbols of formal logic for "or" and "and" without explanation seems a bit obscure. NickyMcLean 21:00, 4 December 2006 (UTC)

Limits

Everyone seems locked into the concept that in exhaustive testing for primality of N, factors up to √N must be considered, and they persist in using a name called Limit for their description of the range of N to be worked through so that they repeatedly talk about √Limit in controlling matters. Since most integers do not have integer square roots this is messy at best and in terms of computational effort, wastefully requires the evaluation of square roots. A better description of the bounds on the possible factors f would be for f^2 <= N rather than f <= √N. And then if you think about the choice of possible factors (as in the division method http://mersennewiki.org/index.php/Trial_factoring) you soon see that only primes should be considered, and it is best to start with the smallest (since more numbers are divisible by 2 than by 3, etc.) working from a small array of prime numbers, and then you need recall only the highest index so far needed, that is f = Prime(i) for i up to LastIndex, the last index for which Prime(LastIndex)^2 <= N, or similar schemes.

And then you might realise that the actual requirement to check N for primality by trial division is as follows: use as factors the primes P(i) with i from 1 to Last such that N < P(Last + 1)^2. For instance, suppose that 5 is the last prime factor being considered as a possible divisor for N. On the face of it, as soon as N reaches 25, you would extend the test list from {2,3,5} to {2,3,5,7}. But this is not necessary. There is no need to test with 7 until 49 = 7*7 is reached, because until then, N = 2*7 need not be tested against 7 because 2 would already be tested for, nor need it be tried for N = 3*7, nor for N = 5*7. Only when N = 7*7 is reached would the test divisions by {2,3,5} not suffice.

In the current context, if MaxFactor is the largest factor that will be considered, then the upper bound for N is MaxFactor^2 and there is no confusion of square roots, especially of numbers that are not perfect squares. Further, if MaxFactor is a prime, say P(i), then the upper bound will be P(i + 1)^2 - 1, though P(i)^2 will do, as would (P(i) + 2)^2 since P(i) + 2 <= P(i + 1) for i > 1. Whichever, the idea is to avoid littering the description with √N and similar. NickyMcLean 21:00, 4 December 2006 (UTC)

modulo 60

Why does the introduction talk about modulo 60 whilst the pseudo code uses modulo 12?

138.251.95.1 09:12, 20 April 2007 (UTC)

Because the algorithm in the introduction includes wheel factorization mod 5, which is avoided in the pseudocode. -- EJ 12:28, 20 April 2007 (UTC)

in the introduction of this article, or of the paper?

138.251.95.1 12:27, 24 April 2007 (UTC)

Indeed, are the two sieve, the one using mod 60 and the one using mod 12, quite different. When implemented, the modulo 12 sieve is noticably faster.

138.251.95.1 12:34, 3 May 2007 (UTC)

anyone? 82.9.63.89 20:49, 13 June 2007 (UTC)

Using modulo 12 instead of modulo 60 seems wrong to me. According to the algorithm description modulo-60 remainders of 5, 25, 55 and 35 should be ignored. However modulo-60 remainders of 5, 25, 55 and 35 correspond to modulo-12 remainders of 5, 1, 7 and 11 respectively. So the pseudo code using modulo-12 will incorrectly flip entries for modulo-60 remainders of 5, 25, 55 and 35. I suggest to change the pseudo code to use modulo-60 —Preceding unsigned comment added by 81.175.82.50 (talk) 08:50, 20 November 2009 (UTC)

Remainders divisible by 5 are ignored by the mod 60 algorithm because the only point of using mod 60 instead of mod 12 is to apply wheel factorization mod 5 as an unrelated optimization. This optimization is (1) completely arbitrary (why not do mod 7 or mod 11 wheel factorization as well?), (2) tangential to the main idea of the algorithm, and (3) it unnecessarily clutters the code and makes it harder to understand what's really going on. If you actually study the explanation of the algorithm, you'll see that the conditions under which the parity of the number of solutions to the three quadratics corresponds to primality only depend on their residue class mod 12. — Emil J. 11:20, 20 November 2009 (UTC)

How is this faster than the Sieve of Eratosthenes?

I have tried both on my computer to compute the primes from 2 to 1000000, and the Sieve of Eratosthenes went nearly twice as fast. I can upload video of me doing it too, and/or upload my code, to a separate website. This discussion may be continued on my talk page... JIMOTHY46_ct 16:54, 25 January 2008 (UTC)

The algorithm is assymptotically faster by a factor of log log N; for practical purposes, that's essentially a constant (and not very large at that), hence it competes with other multiplicative constants representing various overheads. The moral is, the relative speed of the sieve of Atkin vs. sieve of Eratosthenes is extremely sensitive to various optimization tricks used in the implementation. To do it justice, take a look at the implementation at [1] (which also includes a similarly optimized implementation of the sieve of Eratosthenes for the purposes of comparison). It is written by D. J. Bernstein, who is not only a coauthor of the sieve of Atkin, but also a very skilled programmer, unbeatable by any human when it comes to this kind of optimization. It's a fairly safe bet that his implementation of either of the two sieves beats yours by an order of magnitude. -- EJ (talk) 17:18, 25 January 2008 (UTC)

It was probably too subtle but Sieve of Atkin#Computational complexity had a piped link on 'O' in O(N/log log N). The link explains asymptotic growth but I have added a clearer link to Asymptotic computational complexity. PrimeHunter (talk) 17:45, 25 January 2008 (UTC)

I believe you now that I saw the code (it was too complicated for me to understand), but it was unfortunate that it wouldn't build properly...

JIMOTHY46_ct 18:02, 25 January 2008 (UTC)

Having implemented both the pseudo code and the algorithm I have, if you look at the discussion above, found that they differ (not insubstantially) in speed. Would it be possible to change them so that they are both the Sieve of Atkin? I shall do this if I can find some time in the next couple of days.

Farpov (talk) 12:14, 14 April 2008 (UTC)

Can someone explain to me how this algorithm can be O(N/loglogN) if the 2D sweep of x and y in the pseudo-code is O(N) already? Jurgen Hissen (talk) 08:20, 15 December 2011 (UTC)

The pseudocode is not O(N/log log N); the sweep has to be done more carefully for that to happen. See the Atkin-Bernstein paper. CRGreathouse (t | c) 03:22, 19 December 2011 (UTC)

Then the pseudocode is not a valid representation of the algorithm and should be corrected or removed. Directing us to the paper is not a solution to this deficit in this article. Since the whole point of the Sieve of Atkins is as a more efficient prime generator, I think that the point of an encyclopedic article about it should, at the very least, include some *valid* presentation of how it achieves that. Since the pseudocode manages to block any chance of the reader might have had to understand the principal computational feature of this algorithm, at this point it constitutes far more harm than benefit. This is also the kind of thing for which "CLEAN-UP" is needed here. 68.36.102.254 (talk) 22:06, 20 March 2012 (UTC)

So fix it, if you don't think it's good enough. CRGreathouse (t | c) 02:09, 21 March 2012 (UTC)

I would if I could but I cannot, because I came here to learn what makes Sieve of Atkins better than the Sieve of Eratosthenes. Alas, this article's misleading content has left me as ignorant as ever of that matter. You see the problem? RBarryYoung (talk) 01:29, 29 March 2012 (UTC)

A Much Simpler formulation of Sieve of Eratosthenes I have spent 15 years of evenings working on this model not really knowing what I was developing. Then I finally caught on to the rational of the Sieve of Eratosthenes. In fact only just now, the 14th of December 2013 at 20:18 MST (AZ, USA) has all of this come to make sense. BUT, after looking at ALL the work of developing faster and efficient algorithms and programs, they all involve the very tedious and repetitive process of division. I have developed an algorithm that exemplifies the Sieve of Eratosthenes to its fullest potential. This method uses absolutely no division and minimal subtraction for alignment purposes and preserves every calculation made for future use. It uses an alternate base than any I see used in current efforts and uses a very exclusive set of numbers. My algorithm is written in VB 6.0 on a laptop. It is self-expanding to locate prime numbers up to 32767 characters long and with minor enhancements can locate prime numbers up to 1.25 million places - in base 10. But, before I can present the algorithm, I must lay a grand foundation that develops a clear understanding of the properties and behavior patterns of prime numbers. After that the algorithm concept is relatively easy to follow. The coding, however, is a bit intense. The code work is relatively small and will probably be the capstone of my frustrated lifelong programming career. The prediction is that as this program begins to process very high order numbers it will run very quietly in the background and progressively step out rather quickly on the number line. I just don't have a computer that I can run this code unfettered. The biggest administrative challenge I have had with this algorithm is developing a way to manage several 100,000 files, one at a time. But after writing the elementary divide and conquer programs and running this algorithm the results are the same. As I write this post, I realize I must commit this algorithm to an e-book. "The Sieve of Bohn The Automation of The Sieve of Eratosthenes" Carl Bohn (talk) 05:20, 15 December 2013 (UTC)

Carl Bohn: A properly implemented Sieve of Eratosthenes never uses division. It only uses addition to step across a "strikeout-list", that's a big part of it's efficiency, which is slightly sub-linear (except for the list allocation which is linear of course). I have written versions in VB myself and would be willing to take a look at what you have, if you so desire (time permitting). (I am on Gmail with the same username as here). RBarryYoung (talk) 19:02, 27 December 2013 (UTC)

Initialization of initial prime numbers

The directions say to initialize it with 2, 3, and 5, but you can do it without initializing 5 and, according to the original paper, you don't need 5 (it says they start looking for prime numbers by considering primes >3) and the pseudo code seems to agree (otherwise the last loop would start at 7 and not 5). What gives? --M1ss1ontomars2k4 03:18, 2 July 2010 (UTC)

Unlike the pseudocode, the description in the "Algorithm" section implements wheel factorization modulo 5 (or rather 60), which requires that prime 5 receives special treatment.—Emil J. 12:22, 2 July 2010 (UTC)

25%12 = 1 so this is an "accepted prime" in the pseudocode. Yet 5*5=25. There should be an edit made then to explain this as later is states that square free checks are not required for 2,3,5 —Preceding unsigned comment added by 99.224.227.22 (talk) 03:09, 1 February 2011 (UTC)

Ambiguity in the lead

The lead states: "[it] marks off multiples of primes squared, rather than multiples of primes". It is unclear at all on the face of it whether it means the multiples of primes are squared, or it is the multiples of the squared primes that are marked. The English parsing is ambiguous here. WillNess (talk) 13:00, 24 August 2011 (UTC)

No takers in half a year?????? WillNess (talk) 08:51, 15 December 2011 (UTC)

It means multiples of the squared prime. I have reworded the lead paragraph to make this clearer. Gandalf61 (talk) 09:48, 15 December 2011 (UTC)

Note that a naive implementation, as in our lede, takes time $\Omega (n)$ and thus the algorithm is no longer $O(n/\log \log n).$ CRGreathouse (t | c) 03:21, 19 December 2011 (UTC)

Timeline issue

"It was created in 2004 by A. O. L. Atkin and Daniel J. Bernstein.[1]"

with [1] being a reference to the 2004 paper.

But the linked code on djb's website has copyright notices of 1999 and the wayback machine has versions of the page from 2003 (at least) that contain the same files, http://web.archive.org/web/20030623074834/http://cr.yp.to/primegen.html.

so maybe 'created' isn't the right word here? — Preceding unsigned comment added by 50.78.244.161 (talk) 16:35, 17 May 2012 (UTC)

Pseudocode

For the pseudocode bit, can we use words and the few commonly accepted mathematical symbols ( - + / ^ etc) used in programming languages? Instead of upside-down letter A's and wierd Greek-looking E's? As far as programming goes I don't think they're even in EBCDIC! You'd have a hard job getting them through any compiler.

The existing example isn't pseudocode, it's just drawn-out maths. For people who haven't learned the more advanced and esoteric maths, pseudocode is a way of mentally drawing one through a process in a simple way, without using symbols and the compressed and intrinsic knowledge of what processes they represent. With an advanced mathematical education, I'm sure the meaning just leaps off the page for you. For everyone else you may as well print a gigantic question mark. Also, it's not usual to use superscript, you'd usually use ^2 for squared ^3 for cubed, ^x for to-the-power-x etc.

Programming languages use words for their routines, for good reasons. So if someone actually understands what this all means, please do us a favour and fix it up nice. 188.29.164.213 (talk) 00:15, 12 October 2013 (UTC)

(Comment by Albert). You are wrong to expect that an algorithm must be understandable by a computer savy, non mathemathical person. Algorithms (like Euler algorithm) pre-date computers by centuries. You're lazy if you don't try to look up the meaning of set `` { `` and the element-of `` epsilon `` symbols. You will need them in most all mathematical text. This said, I agree that there should be a sort of consensus about the layout and symbols in pseudo code. E.g. Knuth has no if's and for's in his pseudocode, only steps. `` If <condition> : `` is better in my opinion, but the C-people will complain that it is not pseudo-code but Python, if it is not offical wikipedia policy. Remainders too are a source of confusion (the mod operator is not used in a satisfactory way, not from the mathematic pov not from the computer scientist). Having some legenda or reference, explaining symbols or notation that could be unfamiliar, would certainly be an improvement.

Regards using superscript. What? You learned in school about superscript notation. The X**Y notation of C and FORTRAN is a cludge. If you look up ** in a FORTRAN manual, you can only understand the explanation if you learned the upperscript notation in school. Why would we go backward and cater for a specific programming language? A description like here is for understanding, not for cut and paste programming. — Preceding unsigned comment added by 80.100.243.19 (talk) 14:31, 19 October 2015 (UTC)

Note you are replying to a post dated 12 October 2013. PrimeHunter (talk) 14:55, 19 October 2015 (UTC)