C++: counting numbers

[Scorpia]

Hi!
I have a sub program where I find every prime numbers between 1..10000. Now in driver program I need to count how many prime numbers I found. How should I do that? I tried different kind of loops but none of thmen works.

Here is my sub program if necessary (num1=1, num2=10000).

bool isPrimeInterval(int num1, int num2)
{
    while (num1 < num2) 
    {
        bool isPrimeInterval = true; 

        if (num1 <= 1) 
        {
            isPrimeInterval = false; 
        }
        else {
            for (int i = 2; i <= num1 / 2; ++i) 
            {
                if (num1 % i == 0) 
                {
                    isPrimeInterval = false;
                    break;
                }
            }
        }

        if (isPrimeInterval)
            cout << num1 << " "; 
        ++num1;
    }
    return 0;

}

[thmm]

You need one function to determine if a number is a prime and call this function inside a loop.
Sth. like this:

#include <iostream>
#include <string>

bool is_prime(int number)
{
  // your logic to determine if a number is prime
  return false; // or true
}

int main()
{
  int counter = 0;
  
  for (int i = 3; i < 10000; ++i)
  {
      if (is_prime(i))
        ++counter;
  }
  std::cout << "Number of primes " << counter << '\n';
}

[markyrocks]

more efficient.

#include <Windows.h>
#include<string>
#include<fstream>
#include<iostream>

using namespace std;

bool isPrime(int n) {
	if (n == 2) { return true; }
	else if (n == 1 || n % 2 == 0) { return false; }
	
	bool isprime = true;

	for (int i = 3; i < sqrt(n) + 1; i += 2) {
		if (!(n % i)) {
			isprime = false;
			break;
		}

	}
	return isprime;
}

int main() {
	int pcount = 0;

	for (int i = 1; i < 1000001; i++) {
		if (isPrime(i)) { pcount++; }
	}
	cout << pcount;
}

[JLBorges]

Using the prime number theorem and a sieve:
https://www.cplusplus.com/forum/general/125078/ (+ giblits improvement)

[markyrocks]

I played around with this alot a few months back and actually for whatever reason revisited it the other day for fun. That sieve method is probably more efficient at smaller numbers but I found that using it to find numbers that were like 999 billion seemed to break it bc its bigger that the max vector size.
Using something like a binary string would probably work better. Harder to deal with but much smaller. Bitset maybe. I'd like to look into that.

Even with numbers that fall within the upper limits of the max vector size seemed to bog down pretty good just bc of the amount of memory used and the colossal number of read and writes involved.

What I posted above is good at determining if a huge number like 999 billion is prime or not. Not really meant to find all primes between 1 and n.

[Scorpia]

Thank you everyone.

markyrocks: I already have a body for bool isPrime where I need to find out is users number prime number. So how do I combine this?

This code below is not working. First section (where I return isprime) is working, but second part (return 0) doesn't.

bool isPrime(int num1)
{
    if (num1 == 2) { return true; }
    else if (num1 == 1 || num1 % 2 == 0) { return false; }

    bool isprime = true;

    for (int i = 3; i < sqrt(num1) + 1; i += 2) {
        if (!(num1 % i)) {
            isprime = false;
            break;
        }

    }
    return isprime;

        bool prime = true;

        if (num1 <= 1) 
        {
            prime = false; 
        }
        else
        {
            for (int i = 2; i < num1; i++)
                if (num1 % i == 0) 
                {
                    prime = false; 
                    cout << num1 << endl;
                    break;
                }
        }

        if (prime == true) 
            cout << num1 << endl;

    return 0;

}

[seeplus]

All code following return isprime; is ignored and never executed.

[lastchance]

#include <iostream>
#include <cmath>
#include <valarray>
using namespace std;

valarray<bool> sieve( int N )
{
   valarray<bool> A( true, 1 + N ); A[0] = A[1] = false;
   if ( N >= 4 ) A[ slice( 4, (N-4)/2+1, 2 ) ] = false;
   for ( int i = 3, imax = sqrt( N + 0.5 ); i <= imax; i += 2 ) if ( A[i] ) A[ slice( i*i, (N-i*i)/(2*i)+1, 2*i ) ] = false;
   return A;
}

int main()
{
   int n1, n2, number = 0;
   cout << "Input n1, n2: ";   cin >> n1 >> n2;
   auto A = sieve( n2 );
   for ( int i = n1; i <= n2; i++ ) if ( A[i] ) number++;
   cout << "Number of primes is " << number << '\n';
}