Get the total number of prime numbers from 1 to 1million

Question

Env: Microsoft Visual Studio. Project type: Run code in a Windows terminal. Print "Hello World" by default.
Running ok while get the total number of prime number from 2 to 100000.
While not able to get the total number of prime number from 2 to 1000000.
It will just return

Hello World!
Hello World from function().

The following is full code.

#include <iostream>
using namespace std;

//c++ program execute from top to buttom. 
void function();

bool isPrimeNumber(int number) {
    
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}


int main()
{
    cout << "Hello World!\n";
    function();
    int c = 0;
    for (int i = 2; i < 100001; i++) {
        bool isPrime = isPrimeNumber(i);
        if (isPrime) {
            c++;
        }
    }
    cout << c << " is the total number of prime numbers \n";
    
    system("pause>0");
}

void function() {
    cout << "Hello World from function().\n";
}

Answer 1

Your program is probably hanging due too long timeout.

As suggested in comments by @NathanPierson it is enough to check primality until i * i <= number which will speedup code greatly.

As commented by @Quimby if you use GCC or CLang compiler then it is worth adding -O3 command line compile option, which does all possible optimizations to make code as fast as possible. For MSVC compiler you may use /GL /O2 options.

Full corrected working code:

Try it online!

#include <iostream>
using namespace std;

//c++ program execute from top to buttom. 
void function();

bool isPrimeNumber(int number) {
    
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}


int main()
{
    cout << "Hello World!\n";
    function();
    int c = 0;
    for (int i = 2; i <= 1000000; i++) {
        bool isPrime = isPrimeNumber(i);
        if (isPrime) {
            c++;
        }
    }
    cout << c << " is the total number of prime numbers \n";
    
    system("pause>0");
}

void function() {
    cout << "Hello World from function().\n";
}

Output:

Hello World!
Hello World from function().
78498 is the total number of prime numbers 

---

It is possible to implement Sieve of Erathosthenes, which is much more faster for multiple-number primality checking, than Trial-Division checking of each individual number.

Sieve was also suggested by @PepijinKramer.

Below is my implementation from scratch of Sieve of Erathosthenes for Prime Counting Function.

I did time comparison of your prime counting function (based on Trial Division) and my (based on Sieve). And figured that for N of 10 000 000 sieved version is 128x times faster!

Also did small optimization to your isPrimeNumber() function by trying only odd divisors in a loop (see i += 2). This way function doubles its speed.

Try it online!

#include <iostream>
#include <vector>
#include <chrono>

bool isPrimeNumber(int number) {
    if (number <= 2)
        return number == 2;
    if ((number & 1) == 0)
        return false;
    for (int i = 3; i * i <= number; i += 2)
        if (number % i == 0)
            return false;
    return true;
}

int PrimeCountA(int last) {
    int c = 0;
    for (int i = 2; i <= last; ++i)
        if (isPrimeNumber(i))
            ++c;
    return c;
}

int PrimeCountB(int last) {
    std::vector<bool> is_composite(last + 1);
    int c = 0, i = 0;
    for (i = 2; i * i < is_composite.size(); ++i)
        if (!is_composite[i]) {
            for (int j = i * i; j < is_composite.size(); j += i)
                is_composite[j] = true;
            ++c;
        }
    for (; i < is_composite.size(); ++i)
        if (!is_composite[i])
            ++c;
    return c;
}

int main() {
    int const n = 10000000;

    auto const gtb = std::chrono::high_resolution_clock::now();
    auto Time = [&]{
        return std::chrono::duration_cast<std::chrono::milliseconds>(
            std::chrono::high_resolution_clock::now() - gtb).count() / 1000.0;
    };
    double tb = 0;
    {
        tb = Time();
        std::cout << "PrimeCountA " << PrimeCountA(n)
            << ", time " << (Time() - tb) << " sec" << std::endl;
    }
    {
        tb = Time();
        std::cout << "PrimeCountB " << PrimeCountB(n)
            << ", time " << (Time() - tb) << " sec" << std::endl;
    }
}

Output:

PrimeCountA 664579, time 4.223 sec
PrimeCountB 664579, time 0.033 sec