C++ finding all prime numbers from 1 to a number entered

Question

So the point is to have the program find and list all prime numbers between 1 and the number you enter. I'm using number_test as the number tested for prime, and divisor and the number to divide by.

I'm not sure what's wrong, as to me it looks functionally the same as the program posted here: Printing prime numbers from 1 through 100 with some minor changes (inputting a number, changing "i" to less than the number entered).

I've been looking for the past three or four days, and I haven't found anything that really answers this question fully, to the degree I need for class. Any help is much appreciated.

#include iostream
#include conio.h
using namespace std;

void main(void){
//Declare variables
int number_entered;
//Get inputs    
cout << "This program lists all prime numbers from 1 through a positive number entered."
 << endl;
cout << "Please enter a positive integer."
 << endl;
cin >> number_entered;
cout << "Displaying all numbers from 1 to " << number_entered
 << endl
 << "Press any key to continue..."
 << endl;
getch();

for(int number_test = 2; number_test < number_entered; number_test++){
    for(int divisor = 2; divisor < number_test; divisor++){
        if(number_test % divisor == 0){
            break;
        }
        else if(number_test % divisor != 0){
            cout << number_test << " ";
            break;
        }
    }
}

getch();
}

`void main` is not legal C++. I also presume your real code has angle brackets around the header file names. — chris, Oct 18 '13 at 16:21
you should search for prime number generation on stackoverflow.com — Tom Swifty, Oct 18 '13 at 18:28

score 9 · Answer 1 · answered Oct 18 '13 at 16:55

You should use the Sieve of Eratosthenes to compute the primes less than n. Begin by making a list of all numbers from 2 to the maximum desired prime n. Then, at each iterative step, the smallest remaining number that hasn't yet been considered is output and all of its multiples are crossed off the list.

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            output p
            for i from p*p to n step p
                sieve[i] := False

This O(n log log n) algorithm is very fast; you should be able to compute the 78498 primes less than a million in less than a second.

score 2 · Answer 2 · answered May 24 '14 at 09:42

A simple C++ Program to find the "N" prime numbers.

    #include  <iostream >
    using  namespace  std;

    int  main()
    {
        int  N;
        cin  >>  N;
        for (int  i =  2;  N > 0;  ++i)
        {
            bool  isPrime  =  true ;
            for (int  j =  2;  j < i;  ++j)
            {
                if (i  % j ==  0)
                {
                    isPrime  =  false ;
                    break ;
                }
            }
            if (isPrime)
            {
                --N;
                cout  <<  i  <<  "\n";
            }
        }
        return  0;
    }

score 2 · Answer 3 · answered Jan 01 '15 at 09:34

Just a small suggestion. Since prime numbers are odd, even numbers can be left out. For example, in below loops, i and j increase by 2 (i +=2) instead of by 1 (i ++).

for (int i=3;i<=numberByUser; i+=2){
    for (j=3;j<=i;j +=2){
        if (i%j==0){
            break;
        }
    }

Bipin B · Answer 4 · 2013-10-18T16:46:14.090

i think in your answer any way one time the loop will terminated(i am talking about the loop checking the whether it is prime or not)once it comes out you don't know whether it made the break or not.So try to make a flag variable and check outside.I ope that will work

for(n=lower+1; n<upper; n++)
 {
    prime = 1;
     for(i=2; i<n; i++)
       if(n%i == 0)
         {
          prime = 0;
           break;
          }
       if(prime)
        printf("\n\n\t\t\t%d", n);
 }

score 0 · Answer 5 · answered Oct 18 '13 at 16:32

for(int number_test = 2; number_test < number_entered; number_test++){
    for(int divisor = 2; divisor < number_test; divisor++){
        if(number_test % divisor == 0){
            break;
        }
        else if(number_test % divisor != 0){
            cout << number_test << " ";
            break;
        }
    }
}

The above code will not show you the prime numbers, it will just show you the number you entered if/when you run into a divisor that is not a factor of the number. For example, if you enter "9", you will start at 2, which is not a factor of 9, so you will show "9" (incorrectly) as a "prime", when it is not.

The easiest method for testing if a number is a prime is by checking all prime numbers below it's square root to see if they are factors of the given number. If none of them are (then none of the non-prime numbers below the given number will be either), the number is a prime number. If it has at least one prime factor less than or equal to it's square root, it is not prime.

Since you are looking to show all primes in a range of [0, X], you can simply check your list of factors as you go along (or do it in reverse, which is effectively what the Sieve of Eratosthenes does).

score 0 · Answer 6 · 2013-10-18T18:22:41.577

When my point was like your one, I wrote this code, it worked. Hope it will help you.

#include <cstdio>
#include <vector>
using namespace std;

vector <int> sn;

bool isPrime(int n) {
        if (n <= 1) {
                return 0;
        }
        if (n == 2) {
                return true;
        }
        if (!(n % 2)) {
                return false;
        }
        for (int i = 2; i*i <= n; i++) {
                if (!(n % i)) {
                        return 0;
                }
        }
        return 1;
}

void primeNumbers(int k) {
        sn.push_back (2);
        int i = 3, j = 1;
        for ( ; j < k + 1; i += 2 && j++) {
                if (isPrime(i)) {
                        sn.push_back(i);
                }
        }
}

int main() {
        int i, k;
        scanf("%d", &k);
        primeNumbers(k);
        for (i = 0; i < sn.size(); i++) {
                printf("%d ", sn[i]);
        }
        return 0;
}

score 0 · Answer 7 · answered Apr 26 '15 at 01:03

int getNumberOfPrimes(int N) {
    bool *numbers = new bool[N-1]();

    for (int i = 2; i <= N/2; ++i) {
        if (numbers[i-2] == true) continue;

        for (int j = i+i; j <= N; j = j+i) {
            numbers[j-2] = true;
        }       
    }

    int count = 0;
    for (int i = 0; i < (N-1); ++i) {
        if (numbers[i] == false) ++count;
    }

    delete []numbers;
    return(count);
}

score 0 · Answer 8 · answered Feb 27 '18 at 15:22

Man I guess I have the simplest methode of this all. Hope it works for you!

#include < iostream >

using namespace std;

int main()
{
  int n, i, j
  cin>>n;  //The max limith
  for(i=2; i<=2; i++)
   {
     for(j=1; j<=i/2; j++)
      if(i%j!=o)
      cout<<i;
   }

 return 0;
}

score 0 · Answer 9 · answered Mar 29 '18 at 15:50

0

If a number has divisors, at least one of them must be less than or equal to the square root of the number. When you check divisors, you only need to check up to the square root, not all the way up to the number being tested.

answered Mar 29 '18 at 15:50

Youssef Essam

1

C++ finding all prime numbers from 1 to a number entered

9 Answers9