Forum > General

eratosthenes sieve homework

(1/1)

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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program primeNumbers;uses Crt;var    n, i, multiply: integer;    sieve: array[2..120] of boolean; begin    clrScr;      write('Imput a number ');    readln(n);     if (n > 0) and (n <= 120) then    begin        for i := 2 to 120 do            sieve[i] := true;        for i := 2 to n do        begin            if sieve[i] then             begin                nasobek := 2 * i;                while multiply <= n do                begin                    sieve[multiply] := false;                    multiply := multiply + i;                end;            end        end;               write('Prime numbers are: ');        for i := 2 to n do        begin            if (sieve[i]) then                write(i, ' ');        end;    end;     repeat    until keyPressed;end.
edit Fix code formatting

Bart:
Here's a naive implementation.

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program primeNumbers;{\$mode tp}uses  Crt; type  TSieve = array[2..120] of Boolean; procedure InitSieve(var ASieve: TSieve);var  i: Integer;begin  for i := 2 to 120 do ASieve[i] := True;end; procedure CalcSieve(var ASieve: TSieve);var  i,j: Integer;begin  {    primes below 120 are    and these must end up with a value of True in the sieve    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,    73, 79, 83, 89, 97, 101, 103, 107, 109, 113,  }  //cross out all multplications of 2,3,4,5 etc.  //a smarter algo would only calculate multiplications of 2,3,5 etc (basically primes)  //this is left as an excercise to the student  for i := 2 to 120 div 2 do  begin    for j := 2 to (120 div i) do    begin      ASieve[i*j] := False;    end;  end;end; function Prime(Index: Integer; ASieve: TSieve): Integer;var  Count, i: Integer;begin  Count := 0;  for i := 2 to 120 do  begin    if ASieve[i] then    begin      Inc(Count);      if (Count = Index) then      begin        Prime := i;        Exit;      end;    end;  end;  //if we get here, no prime is found  Prime := 0;end; var    Number, APrime: integer;    Sieve: TSieve;begin    ClrScr;    InitSieve(Sieve);    CalcSieve(Sieve);    write('Imput a number ');    readln(Number);    APrime := Prime(Number, Sieve);    if APrime > 0 then      writeln('Prime number ',Number,' = ',APrime)    else      writeln('No prime found with index ',Number);    write('Press any key ... ');    repeat    until KeyPressed;    writeln;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:

--- Quote from: Ghostyy on December 07, 2023, 06:32:20 pm ---if the imput is, say 11, it has to display the first 11 prime numbers, not prime numbers up until 11.

--- End quote ---
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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---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:

--- Quote from: 440bx on December 07, 2023, 08:49:01 pm ---
--- Quote from: Ghostyy on December 07, 2023, 06:32:20 pm ---if the imput is, say 11, it has to display the first 11 prime numbers, not prime numbers up until 11.

--- End quote ---
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.

--- End quote ---

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.