C++ Prime Numbers from 3 to n

Question

I wrote this code to print all prime numbers between 3 and 'n' inputted by the user, but upon running, it produces nothing.

Can you please help?

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int candidate = 3; candidate < n; ++candidate)
    {
        bool isPrime = true;
        for (int x = 2; x < n; x++)
        {
            if (candidate % x == 0)
            {
                isPrime = false;
            }
        }

        if (isPrime)
        {
            cout << n << "";
        }
    }
}

As mentioned why not print out `candidate`, also what is the purpose of `""` after the printout of `n`, should it not be a new line or some other space? — Tommy Andersen, Oct 18 '17 at 07:18
Print `candidate` instead of `n`. Also, You are forgetting a base case *2 is also a prime number*. If `n=2`, then your program will not print the same. — Ishpreet, Oct 18 '17 at 09:48

user2736738 · Answer 1 · 2017-10-18T08:14:19.717

One thing you should know. For checking whether n is prime if we start checking by division operation then you shouldn't check more than sqrt(n).

    for (int candidate = 3; candidate < n; ++candidate)
    {
        bool isPrime = true;
        for (int x = 2; x*x < candidate; x++)
        {
            if (candidate % x == 0)
            {
                isPrime = false;
                break;
            }
        }

        if (isPrime)
        {
            cout << candidate << "";
        }
    }

Better way is to use Sieve of Eratosthenes for this:

isPrime: initialize with all true
for(int i=2;i*i<=n;i++)
  for(int j =i*i;j<=n;j+=i)
    isPrime[j]=false;   // the if was not needed.

Now you know which are primes between 3 and n.

you don't need the `if` in your sieve algorithm: just set `isPrime[j]=false` anyhow. This is presumably faster than the branch. — Walter, Oct 18 '17 at 08:08

Walter · Answer 2 · 2017-10-20T08:42:34.050

2

There are several efficiency savings possible in your code. The most efficient method (apart from using a pre-calculated look-up table for small (<1000) n) is the sieve of Erastosthenes.

A very naive version of this algorithm (see also the answer by coderredoc)

std::vector<int> primes(int n)
{
    std::vector<bool> is_prime(n+1,true);
    for(auto divisor=2; divisor*divisor <= n; ++divisor)
        for(auto candidate=divisor*divisor; candidate <= n; candidate+=divisor)
            is_prime[candidate]=false;
    std::vector<int> result;
    for(auto candidate=2; candidate <= n; ++candidate)
        if(is_prime[candidate]) result.push_back(candidate);
    return result;
}

essentially reverses the loops over candidates and divisors compared to your original algorithm, but only tests for divisors satisfying divisor*divisor<=candidate.

This algorithm can be substantially improved by realizing that we only need to test for prime divisors (which is the main trick of the sieve)

std::vector<int> primes(int n)
{
    std::vector<bool> is_prime(n+1,true);
    for(auto divisor=2; divisor*divisor <= n; ++divisor)
        if(is_prime[divisor])
            for(auto candidate=divisor*divisor; candidate <= n; candidate+=divisor)
                is_prime[candidate]=false;
    std::vector<int> result;
    for(auto candidate=2; candidate <= n; ++candidate)
        if(is_prime[candidate]) result.push_back(candidate);
    return result;
}

which cuts down on the testing for large n. A further efficiency saving (by a factor ~2 in space and time) is possible by avoiding even candidates and divisors:

std::vector<int> primes(int n)
{
    if(n<2) return {};
    if(n==2) return {2};
    std::vector<bool> is_prime((n+1)>>1,true);
    for(auto divisor=3; divisor*divisor <= n; divisor+=2)
        if(is_prime[divisor>>1])
            for(auto candidate=divisor*divisor; candidate <= n; candidate+=2*divisor)
                is_prime[candidate>>1]=false;
    std::vector<int> result(1,2);
    for(auto candidate=3; candidate <= n; candidate+=2)
        if(is_prime[candidate>>1]) result.push_back(candidate);
    return result;
}

This algorithm has a poor memory access pattern (into the is_prime[]), which becomes a problem for very large n. A more sophisticated method, segmented sieve, can avoid that, see the above link.

edited Oct 20 '17 at 08:42

answered Oct 18 '17 at 09:16

Walter

44,150
20
113
196

Still +1 though for a neat answer =) – Sergey.quixoticaxis.Ivanov Oct 18 '17 at 15:45
1

@Sergey.quixoticaxis.Ivanov actually, I experimented with that and replaced it with `std::vector`. To my surprise the code was slower (Apple clang compiler, -O3). – Walter Oct 18 '17 at 16:07
it's strange, I don't know about `char`, but on Intel i5 6600 and Intel i7 4790k changing `::std::vector` to `bool*` (I don't "push_back" anything and pre-allocate buffer for `is_prime` only once) had a great affect both on msvc and Intel C++ 17. – Sergey.quixoticaxis.Ivanov Oct 18 '17 at 16:12
*effect (sorry for this ^-^) – Sergey.quixoticaxis.Ivanov Oct 18 '17 at 16:20
1

I also experimented with that (though using `std::unique_ptr is_prime{new bool[n+1]};`) and then initializing with `true`. I guess, the latter is inefficient (better initialise 8 bytes at a time, which is presumably what `std::vector` does). But the initialization shouldn't dominate the costs. At any rate, this too was slower then `std::vector` perhaps the msvc or Intel (icpc) implementations of `std::vector` are inferior? – Walter Oct 18 '17 at 21:16
Can't say it for sure but I doubt it. `::std::vector` without `reserve()` would copy on capacity exhaustion and also `::std::vector` involves proxy usage. It imho should be slower then array on any compiler. I can post my code: if u can run it with clang and see how it works, it would be awesome) – Sergey.quixoticaxis.Ivanov Oct 18 '17 at 21:30
@Sergey.quixoticaxis.Ivanov sure, happy to run tests. One point of `vector` is that is uses only one bit per `bool`, i.e. has much smaller cache usage. This may be critical in this algorithm, since the memory access pattern to `is_prime` is quite erratic, so smaller memory footprint by a factor 8 gives (up to a) factor 8 fewer cache misses, which is huge in terms of efficiency. – Walter Oct 19 '17 at 10:11
Whether or not `vector` is space optimized and (hence uses a proxy to assign to individual elements) is implementation dependent. However, as the proxy should be fully inline, all that should be optimally resolved at compile time. So, if it is implemented such that each `bool` is represented by a single bit, then `is_prime[i]=false` involves some bit-wise operations, but they are all inlined. – Walter Oct 19 '17 at 10:17
`::std::vector` _is recommended_ to be space optimized. At least I think so, while reading my copy of ISO from mobile ) I'll post my code somewhere and provide a link when I get to PC. – Sergey.quixoticaxis.Ivanov Oct 19 '17 at 11:00
My bad. I thoroughly re-tested my code on both MS and Intel compilers. It looks like `::std::vector` does better. I guess that your assumption about cache locality was correct. For `vector` my code generates first 10 million primes in around 2.5 seconds (avg over 100 runs), and for `bool*` it runs 3.6 seconds (same avg over 100 runs). – Sergey.quixoticaxis.Ivanov Oct 19 '17 at 13:26
@Sergey.quixoticaxis.Ivanov Are you sure? For the first 10 million primes, my code takes about 2.5ms not 2.5s (it also depends whether you merely count them or also store them). – Walter Oct 19 '17 at 16:25
I store them. My code is naive, at least I think it could be much better (it was a self-excercise "write prime generator in 15 minutes") – Sergey.quixoticaxis.Ivanov Oct 19 '17 at 16:31
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/157084/discussion-between-sergey-quixoticaxis-ivanov-and-walter). – Sergey.quixoticaxis.Ivanov Oct 19 '17 at 17:14

J...S · Answer 3 · 2017-10-18T17:10:38.137

1

Change your inner loop from

    for (int x = 2; x < n; x++)
    {
        if (candidate % x == 0)
        {
            isPrime = false;
        }
    }

to

    for (int x = 2; x < candidate; x++)
    {
        if (candidate % x == 0)
        {
            isPrime = false;
            break;
        }
    }

otherwise x would eventually become candidate itself and candidate%candidate is 0 which would cause isPrime to become false.

The break statement is used because after being sure that the number is not prime, there's no need of further iterations.

And since you consider only numbers from 3, you could change your outer loop to save some iterations like

for (int candidate = 3; candidate < n; candidate+=2)

This would increment candidate by 2 each time. This is okay because no even numbers greater than 2 are not prime.

Also, if the range of numbers you are considering is inclusive of n, you may modify the outer for loop to

for (int candidate = 3; candidate < n; candidate+=2)

to consider n as well.

edited Oct 18 '17 at 17:10

answered Oct 18 '17 at 07:20

J...S

5,079
1
20
35

1

This is wrong. It will only print ONE prime number. He wants to print all of them. – Martin Bonner supports Monica Oct 18 '17 at 07:44
@MartinBonner Oops! I had not realised it. Edited. Thanks for pointing out. – J...S Oct 18 '17 at 08:34
2

I would just delete the old erroneous answer, rather than leaving it in place. – Martin Bonner supports Monica Oct 18 '17 at 08:51
Removed the old part – J...S Oct 18 '17 at 17:12

Sébastien Barré · Answer 4 · 2017-10-18T07:37:15.313

0

It's not recommended to use using namespace std; — because this imports all of the identifiers from std. See this question on Stack Overflow.

Should the end condition of the second loop be candidate instead of n, i.e.

for (int x = 2; x < candidate; x++)//not before N prime numbers divine up to them
{
    if (candidate % x == 0)
        isPrime = false;
}

Shouldn't you put out candidate instead of n

edited Oct 18 '17 at 07:37

answered Oct 18 '17 at 07:28

Sébastien Barré

154
1
12

FirePower · Answer 5 · 2017-10-18T14:17:21.250

I think this should work

#include <iostream>
#include <vector>


int main()
{
    //setup start parameters
    //test sequence
    std::vector<int> test_sequence {2};




    int end_number, start_number;
    start_number = 3;
    //take wished end number
    std::cin >> end_number;

    // test is wished number smaler than start number
    if (start_number < end_number)
    {
        // loop which goes trough every number between start and end number
        for (start_number; start_number <= end_number; start_number++)
        {
            bool isPrime = true;
            //test is this number prime
            for (int n = 0; n < test_sequence.size(); n++)
            {
                if (start_number % test_sequence[n] == 0 && start_number != test_sequence[n] )
                {
                isPrime = false;
                }
            }

            if (isPrime)
            {
                std::cout << start_number << std::endl;
                //hold result for next test
                test_sequence.push_back(start_number);
            }
        }

    }
    else
    {
    std::cout << "Wrong input";
    }

}

Result for first 200

*execution time 10.115 s* This is horrible. For the primes up to 200 a good algorithm needs about 4μs (one any modern CPU), more than 10M times shorter. — Walter, Oct 18 '17 at 16:14
10 million first primes can be calculated in 3-4 seconds with a naive algorithm, written as a short exercise — Sergey.quixoticaxis.Ivanov, Oct 18 '17 at 17:15
It's not time which needed to calculate results, I just didn't enter end number immediately when program started. — FirePower, Oct 18 '17 at 17:28

C++ Prime Numbers from 3 to n

5 Answers5

Better way is to use Sieve of Eratosthenes for this: