0

I am trying to get my Sieve of Eratosthenes program to output only the first n prime numbers that the user requests. The Sieve works just fine on its own- it correctly outputs the first 100 prime numbers (as in my array below), but the counter variable in the last loop isn't working correctly and I can't figure out why. For example, if the user enters "5" for n, only the first 3 primes will be printed.

Can someone help me figure out my mistake? My intent was to have "count" be a very simple counter that would increment by 1 each time, until it reached n.

int n;
cout << "Enter the number of primes you want to print:\n";
cin >> n;

int arr[100] {0};

for (int i = 2; i <= sqrt(100); i++)
{
    if (arr[i] == 0)
    {
        for (int j = 2; i*j<100; j++)
            arr[j*i] = 1;
    }
}

for (int i = 3, count = 0; i <= 100 && count != n; i++, count++)
{
    if (arr[i] == 0)
        cout << i << '\n';
}
3
  • 2
    5 for n ...is an input. you say 3 is output. what did you expect? i.e what is wrong with the output? By the way, is 3 the correct number of prime numbers for numbers <= 5?
    – 2785528
    Jul 21, 2021 at 23:21
  • Be careful. Your array is only 100 and yet you let the user type in any number. In reality, there are 25 primes less than 100 so the largest value they should be allowed to enter is 25. This page has a list of how many primes below a certain size array: primes.utm.edu/howmany.html Jul 21, 2021 at 23:52
  • That is a good point about the user input, thank you.
    – Asta Lee
    Jul 22, 2021 at 0:28

2 Answers 2

3

You should count only prime numbers, not all numbers.

Also the range of i for looping should be corrected. The first prime number is 2 and the element arr[100] is not available.

for (int i = 2, count = 0; i < 100 && count != n; i++) // don't increment count here
{
    if (arr[i] == 0)
    {
        cout << i << '\n';
        count++; // count a prime number here
    }
}
1
  • Oh my gosh this is exactly what I was looking for. I was incrementing count in the wrong place. Thank you very much, it works now.
    – Asta Lee
    Jul 21, 2021 at 23:41
1

I have a solution using Ada, which may give you some help. I have created a function named Is_Prime that returns a TRUE when the parameter passed to it is a prime number and FALSE when it is not.

Following is the package specification containing the declaration of Is_Prime. Consider the package specification to be similar to a C header file.

package Primality is
   function Is_Prime(Num : Positive) return Boolean;
end Primality;

The implementation of the function is in the package body, corresponding roughly to a C .c file.

-----------------------------------------------------------------------
-- Primality Body                                                    --
-----------------------------------------------------------------------
with Ada.Numerics.Generic_Elementary_Functions;

package body Primality is
   function Is_Prime (Num : Positive) return Boolean is
      package Flt_Funcs is new Ada.Numerics.Generic_Elementary_Functions
        (Float);
      use Flt_Funcs;

      T      : Integer          := 2;
      Limit  : constant Integer := Integer (Sqrt (Float (Num)));
      Result : Boolean          := True;
   begin
      if Num = 2 then
         Result := True;
      else
         while T <= Limit loop
            if Num mod T = 0 then
               Result := False;
               exit;
            end if;
            T := T + (if T > 2 then 2 else 1);
         end loop;
      end if;
      return Result;
   end Is_Prime;
end Primality;

Ada allows the programmer to name the "main" file anything he or she wants. Following is the "main" file to allow the user to specify the number of primes to be output.

with primality; use primality;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;


procedure List_Primes is
   count : Natural;
   Num   : Positive := 2;
begin
   Put("Enter the number of primes you want to print: ");
   Get(count);
   while count > 0 loop
      if Is_Prime(Num) then
         Put_Line(Num'Image);
         count := count - 1;
      end if;
      Num := Num + (if Num = 2 then 1 else 2);
   end loop;
end List_Primes;

The output of a sample run is:

Enter the number of primes you want to print: 20
 2
 3
 5
 7
 11
 13
 17
 19
 23
 29
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.