Recent

Author Topic: eratosthenes sieve homework  (Read 789 times)

Ghostyy

  • Newbie
  • Posts: 1
eratosthenes sieve homework
« on: December 07, 2023, 06:32:20 pm »
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
« Last Edit: December 09, 2023, 01:12:10 pm by Ghostyy »

Bart

  • Hero Member
  • *****
  • Posts: 5234
    • Bart en Mariska's Webstek
Re: eratosthenes sieve homework
« Reply #1 on: December 07, 2023, 07:35:11 pm »
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

  • Hero Member
  • *****
  • Posts: 3860
Re: eratosthenes sieve homework
« Reply #2 on: December 07, 2023, 08:49:01 pm »
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.


(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.1 both fixes) on Windows 7 SP1 64bit.

Bart

  • Hero Member
  • *****
  • Posts: 5234
    • Bart en Mariska's Webstek
Re: eratosthenes sieve homework
« Reply #3 on: December 07, 2023, 10:18:44 pm »
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

  • Sr. Member
  • ****
  • Posts: 325
Re: eratosthenes sieve homework
« Reply #4 on: December 09, 2023, 11:51:27 am »
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.
« Last Edit: December 09, 2023, 12:01:06 pm by MathMan »

 

TinyPortal © 2005-2018