eratosthenes sieve homework

[Ghostyy]

Hey everyone, I have a little problem. I have to code the eratosthenes sieve, and if the imput is, say 11, it has to display the first 11 prime numbers, not prime numbers up until 11. I know I need to use array, but I also need to implement the mod function somehow. Could someone please help? Thanks in advance.

/Should also note that I found this code on this forum and tried to work with it, but now I unfortunately cannot find the original person who posted it. The original was in Czech.

edit: Thanks to everyone that helped

Code: Pascal  [Select][+][-]

1. program primeNumbers;
2. uses Crt;
3. var
4.     n, i, multiply: integer;
5.     sieve: array[2..120] of boolean;
6. begin
7.     clrScr;
8.  
9.  
10.     write('Imput a number ');
11.     readln(n);
12.  
13.     if (n > 0) and (n <= 120) then
14.     begin
15.         for i := 2 to 120 do
16.             sieve[i] := true;
17.         for i := 2 to n do
18.         begin
19.             if sieve[i] then
20.             begin
21.                 nasobek := 2 * i;
22.                 while multiply <= n do
23.                 begin
24.                     sieve[multiply] := false;
25.                     multiply := multiply + i;
26.                 end;
27.             end
28.         end;
29.  
30.      
31.         write('Prime numbers are: ');
32.         for i := 2 to n do
33.         begin
34.             if (sieve[i]) then
35.                 write(i, ' ');
36.         end;
37.     end;
38.  
39.     repeat
40.     until keyPressed;
41. end.                                              
42.  

edit Fix code formatting

[Bart]

Here's a naive implementation.

Code: Pascal  [Select][+][-]

1. program primeNumbers;
2. {$mode tp}
3. uses
4.   Crt;
5.  
6. type
7.   TSieve = array[2..120] of Boolean;
8.  
9. procedure InitSieve(var ASieve: TSieve);
10. var
11.   i: Integer;
12. begin
13.   for i := 2 to 120 do ASieve[i] := True;
14. end;
15.  
16. procedure CalcSieve(var ASieve: TSieve);
17. var
18.   i,j: Integer;
19. begin
20.   {
21.     primes below 120 are
22.     and these must end up with a value of True in the sieve
23.     2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
24.     31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
25.     73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
26.   }
27.   //cross out all multplications of 2,3,4,5 etc.
28.   //a smarter algo would only calculate multiplications of 2,3,5 etc (basically primes)
29.   //this is left as an excercise to the student
30.   for i := 2 to 120 div 2 do
31.   begin
32.     for j := 2 to (120 div i) do
33.     begin
34.       ASieve[i*j] := False;
35.     end;
36.   end;
37. end;
38.  
39. function Prime(Index: Integer; ASieve: TSieve): Integer;
40. var
41.   Count, i: Integer;
42. begin
43.   Count := 0;
44.   for i := 2 to 120 do
45.   begin
46.     if ASieve[i] then
47.     begin
48.       Inc(Count);
49.       if (Count = Index) then
50.       begin
51.         Prime := i;
52.         Exit;
53.       end;
54.     end;
55.   end;
56.   //if we get here, no prime is found
57.   Prime := 0;
58. end;
59.  
60. var
61.     Number, APrime: integer;
62.     Sieve: TSieve;
63. begin
64.     ClrScr;
65.     InitSieve(Sieve);
66.     CalcSieve(Sieve);
67.     write('Imput a number ');
68.     readln(Number);
69.     APrime := Prime(Number, Sieve);
70.     if APrime > 0 then
71.       writeln('Prime number ',Number,' = ',APrime)
72.     else
73.       writeln('No prime found with index ',Number);
74.     write('Press any key ... ');
75.     repeat
76.     until KeyPressed;
77.     writeln;
78. end.

We first init the sieve to assume all numbers are indeed primes.
Then we calculate all possible multiplications of all numbers (up to the half of the array max value) and set these to False (it is NOT a prime).
Then we iterate over the sive to find the n-th prime, and if no such prime is in the array, we display an error message.

A smarter algorithm to  setup the sieve (only crossing out multiples of primes (notice: after each run (crossing out all even numbers), the frist index in the sieve that is still True must be a prime) is left as an excercise to you.
And it probaly is a MUST to implement such an algorithm.

Also, bonus point probably can be achieved by using named constants for the lower and upper limit of the TSieve type.
And maybe even better to specify a specific type that covers this range and use that type in the definition of the TSieve type.
Teachers just love that.

Bart

[440bx]

if the imput is, say 11, it has to display the first 11 prime numbers, not prime numbers up until 11.

That requirement is a bit of a problem because there is no formula that yields the number of primes found in an interval (2..n) much less one that given a desired number of primes gives the max of the interval (n) (presuming the interval starts with the first prime.)

if the prime index is limited to 1000 then the array can be limited to 7919 (which is the 1000th prime)

The professor should specify what the highest prime index the problem should handle can be.

[Bart]

One of my "fun" units contais this declaration:

Code: Pascal  [Select][+][-]

1. StaticPrimes: Array[1..10000] of Integer = (...

(StaticPrimes[10000] = 104729 b.t.w.)
That would make the last part of the homework assignment considerably easier...

Bart

[MathMan]

if the imput is, say 11, it has to display the first 11 prime numbers, not prime numbers up until 11.

That requirement is a bit of a problem because there is no formula that yields the number of primes found in an interval (2..n) much less one that given a desired number of primes gives the max of the interval (n) (presuming the interval starts with the first prime.)

if the prime index is limited to 1000 then the array can be limited to 7919 (which is the 1000th prime)

The professor should specify what the highest prime index the problem should handle can be.

Not sure that the teacher will do that, because

 1. Pi( n  ) ~ n / ln( n )
 2. for all n>1 there is at least one prime in [ n+1, 2*n )

So, one could do an estimate for the array size via 1., do the sieving by Erathostenes on that array and count the resulting primes detected. If that is less than the desired number then double the range and sieve the upper half too. This is trivial, because you already know all primes who's multiples have to be evicted from the upper half.

With a very high chance, you'll find the searched for k-th prime in the upper half (if you haven't found it already in the first step).

One could optimise this by a better initial approximation.

If one can not resolve 1. for a good starting point in n, then there is the following simple alternative.

Start with '2', which is the first prime, but not the 11th from the example. Then double the range and sieve by Erathostenes. That should yield '3' as the second prime - still not the 11th. Double and sieve again, which should yield '5' & '7' as 3rd & 4th prime. Etc.

I'm pretty sure the teacher / professor is heading for some dynamic solution.