Help with prime number code C++

[kyletrugliaeder]

Hey everyone. I am having trouble with my code and I do not understand what is going on. I wrote a code where I enter a number and it will tell me if it is a prime number or not. The only problem is, when I enter a huge number like 10000000000000000000000000000000, it will say that the number is a prime number, which it shouldn't be because it can be divided by 10.

#include "pch.h"
#include <iostream>
using namespace std;

int main()
{
int i, no;
cout << "Enter any number (remember, if you enter an even number, it will not be prime: ";
cin >> no;
if (no == 1)
{
cout << "Smallest prime num is 2";
}
for (i = 2; i < no; i++)
{
if (no%i == 0)
{
cout << "Not prime number";
break;
}
}
if (no == i)
{
cout << "Yes, Number is Prime";
}
return 0;
}

[lastchance]

http://www.cplusplus.com/reference/limits/numeric_limits/

[Ganado]

If the int has already overflowed, you can't check its numeric limits :)

Luckily, the (cin >> no) call will fail before integer overflow occurs, so you can at least check that.

// Example program
#include <iostream>
#include <string>

int main()
{
    using namespace std;
    
    int no;
    if (cin >> no)
    {
        cout << "Valid number: " << no << '\n';
    }
    else
    {
        cout << "Invalid number!\n";   
    }
}

100000000000000000000000000000000000
Invalid number!

2147483647
Valid number: 2147483647

2147483648
Invalid number!

Edit: Oh, I think I see what lastchance is getting at now. Data types in C++ do not have infinite size, so they can't hold arbitrarily large numbers. For example, the maximum integer you can successfully type in is usually 2³¹-1 (assuming 4-byte signed int), which is 2147483647.

Using unsigned 64-bit integers (e.g. unsigned long long int on most platforms), you can get around 2^64 - 1 as the maximum number. Still not arbitrarily long, however.

If you want to be able to enter arbitrarily large numbers, do a search for "bignum" libraries.

[jonnin]

check to see if your machine has a 128 bit register or if it can make one from 2 64 bit registers with any kind of assembly command.
128 singed goes up to 170,141,183,460,469,231,731,687,303,715,884,105,727 or ~twice that for unsigned.
If that won't do you can make your own big-int class from 2 64 bit values to emulate it, or get a hard core bigint class but be wary of those, many are written byte-wise not maxregister-wise and are inefficient.

[dhayden]

Keep in mind that even if you could represent a number that big, it would take a 4GHz processor running your program at least 80 quadrillion years to determine that a number that big is prime, although it would be far less if it's divisible by a small number like 10.

I'd just give it smaller numbers.

Helpful hint: 10 bits is a little more than 3 digits. So to figure out how big 64 bit ints are:
64 bits = 60+4 bits.
60 bits ~ 60/10*3 = 18 digits.
4 bits = 16.

So 64 bits ~ 16 * 10¹⁸ values.

So I'd just stick to values of 18 digits or less.

[markyrocks]

There has to be a more efficient way to do this. I been thinking about this for a bit and i var shouldn't increment higher than the number/2. Bc no number higher than that can possibly divide into said number cleanly.

The other thing is once the number makes it past the no % 2 check, the i variable should at the very least only increment to odd numbers skipping anything that ends in a 5 (after i > 5). Ideally you'd want i to only increment to prime numbers. I only say that bc any number that makes it past % 2,3,5,7 is either going to be prime or divisible by a prime number. It probably makes sense to either find a list or generate a list of prime numbers between 2 and whatever the maximum number/ 2 and use file stream to determine what the next i value would be. Might not be a terrible idea to check to see if the sqrt of the number is a whole number b4 you start incrementing aswell.

[mbozzi]

I've been thinking about this for a bit and i var shouldn't increment higher than the number/2

Even better than number/2 is ceil(sqrt(number)), because all divisors come in pairs.

There has to be a more efficient way to do this.

There's lots of enormously sophisticated ways to approach this problem, if you really find it interesting:
https://en.wikipedia.org/wiki/Primality_test

[markyrocks]

this is something quick that i came up with that finds primes. Its definitely slow but my laptop isn't the fastest either but it definitely finds primes not exactly what the op is looking for but i checked it against the first 10000 known primes and the 10000th one is exactly the same so i'd assume the ones in the middle are the same as well.

struct primeNumbers {

	vector<int> primes;

	 int max = 600000000;

	primeNumbers()
		: primes{} {}

	void generatePrimes(){
	
		primes.push_back(2);
		primes.push_back(3);
		bool isPrime = false;
		double _sqrt{};

		for (int x = 5; x < max; x+=2) {
			_sqrt = sqrt(x);
			isPrime = true;
				for (int ds : primes) {
					if (x % ds == 0) { isPrime = false; break; }
					if (ds > _sqrt){break;}
				}
				if (isPrime) { primes.push_back(x); }
				//if (primes.size() == primes.max_size() - 1) { break;}
				//if (primes.size() == 100000) { break; } //for testing
		}
	
		cout << "number of primes = " << primes.size();
	}
};

int main() {

	primeNumbers p;
	p.generatePrimes();
}

after about an hr i found about 30 million primes and x is 600 million

[jonnin]

goodness, that is slow. This isnt the best code; its something I did ages ago for a similar homework posted here, but I just did x = 600M in seconds.

using the world's worst timer, the dos prompt itself (prompt $t$g command):

 9:56:35.37>a
11113 is prime
 9:56:44.60>

  vector<bool>&  initpn()
  {	  
  unsigned long long i,j, s = 600000000; 
  static vector<bool> pn(s,true); 
  for(i = 3; i < pn.size(); i+=2)
  {
     if(pn[i])
      for(j = i*2; j < pn.size(); j+=i)
         pn[j] = false; 	
  }
   return pn;  
  
  }  
    
  int main()
  {
	vector<bool> &p = initpn();
    unsigned long long u = 11113;
    //cout << "enter number\n";
	//cin >> u;
	if(p[u]) cout << u <<" is prime\n";
	else cout << u << " is not prime\n";
     	
  }

what why etc..
- vector bool is often optimized to use 1 bit per entry by the compiler.
- it does not test, it just sets. take 2: then loop every other number and set it to false. then take 3, loop every 3rd number and set that to false. then take 5 (the next true value), loop every 5th number and set them all false. then take 7 (the next true value so far)... etc.... this is the 'sieve of some guy whos name I cannot spell' or 'prime sieve' for short, a well known algorithm. Its one of the very cool extremely old algorithms, like the square root, that existed almost since the wheel and fire were new. you can manually set 1 and 0 if you like, gigo and all that.
- at some point even vector bool won't hold any more, of course.

edit, just realized a little tweak:
for(j = i*3; j < pn.size(); j+=i*2)//3-> 9, 15, 21 ... 5 -> 15, 25, 35, ... not much but skips the redundant evens. have to add a loop to do the even's one time, though. This pulls 600M to < 10 sec and 2^32 to < 3 min on my somewhat wimpy work laptop.

[TheToaster]

If you only need the primes to be calculated at compile time, you can use some recursive template metaprogramming to do the trick.

[markyrocks]

That is tricky. Very nice tho. Can't wait to get home and play around with it. Curious to see how fast it will find up to max int. I'm wondering if part of the reason what I posted is so slow is bc im running it on the debug? I realize that i do have some unnecessary calculations in there. Like using sqrt every loop doesn't help anything. When I run in debug it shows cpu usage and its not even close to 100. Definitely wondering if i compiled it how much of a difference it would make. I definitely like the above concept tho.

[mbozzi]

If you only need the primes to be calculated at compile time, you can use some recursive template metaprogramming to do the trick.

You can, but only if you hate your job, because you'd be fired on the spot ;-)

[lastchance]

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

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

int main()
{
// const int N = 600000000;
   const int N = 1000000;
   
   clock_t t0 = clock();
   auto A = sieve( N );
   double t = (double)( clock() - t0 ) / CLOCKS_PER_SEC;

   cout << "Sieve took " << t << " seconds\n\n";

   int n = 0;   for ( int i = 0; i <= N; i++ ) if ( A[i] ) n++;   cout << n << " primes\n";

   int pmax = 50;
   cout << "Primes less than " << pmax << ": ";
   for ( int j = 0; j < pmax; j++ ) if ( A[j] ) cout << j << " ";
}

Slightly faster, but more obscure, version:

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

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

int main()
{
// const int N = 600000000;
   const int N = 1000000;
   
   clock_t t0 = clock();
   auto A = sieve( N );
   double t = (double)( clock() - t0 ) / CLOCKS_PER_SEC;

   cout << "Sieve took " << t << " seconds\n\n";

   int n = 0;   for ( int i = 0; i <= N; i++ ) if ( A[i] ) n++;   cout << n << " primes\n";

   int pmax = 50;
   cout << "Primes less than " << pmax << ": ";
   for ( int j = 0; j < pmax; j++ ) if ( A[j] ) cout << j << " ";
}

[jonnin]

debug mode is absolutely a big deal for speed.
but those push-back calls are likely one of your performance hits. Note that I preallocated my vector to avoid that.

the cpu can sort of do branch prediction, and the compiler can assist it as well, but even so too many conditional jumps will slow you down. I have only one.

A list of primes forces you to search it to do your is-prime. I have a O(1) lookup to do that, but waste space ... this is the time/space tradeoff at work.

The valarray trick is very nice too. They are a powerful and often forgotten tool.

[markyrocks]

@jonin your computer must be a beast. Either that or vs 19 is just a dog lol. It literally takes my computer 6 min 30 seconds just to make it through this loop once....

vector<bool> primes(600000000,true);
		for (int i = 2; i < primes.size(); i += 2) { primes[i] = false; }

lol

i will say that I made some changes to the code i posted above and it finds all primes between 5 and 600,000,000 in 10 minutes so thats a significant improvement. jonin run my code on your computer and do a time comparison for lols.

[jonnin]

C:\c>g++ -O3 tools.cpp
C:\c>prompt $t$g
 8:49:03.89>
 8:49:05.39>a
number of primes = 31324703
 8:52:50.10>

what are you using? I consider the machine I use to be a little weak; its a 4 year old work provided laptop. I have a high end desktop that would do these notably faster. Did you forget to turn on optimize? VS19 should produce a very fast executable if in release mode and set to favor speed.

Processor: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz (4 CPUs), ~2.8GHz
Memory: 16384MB RAM

[dhayden]

I apologize for hijacking this thread, but fro some reason I'm unable to create new posts. The form opens up okay and I can type into the subject and body boxes, but the character counter doesn't increment and if I preview it, I see nothing. Does anyone know what might be wrong?

Thanks,
Dave

[TheToaster]

@dhayden
It seems the character count and preview are broken for me as well, however I am still able to create a new post. I am just not able to preview it.

[markyrocks]

C:\c>g++ -O3 tools.cpp
C:\c>prompt $t$g 8:49:03.89>
8:49:05.39>a
number of primes = 31324703
8:52:50.10>

So that is pretty good then? Idk exactly which cpu i have in my laptop but I think its a 7200u. With 16 gb gskill ram and a Samsung 850 evo ssd. It is a few years old but I've always thought it was relatively fast for most basic tasks. It does get bogged down under heavy loads.

I guess I'll try to turn on release mode and play with the settings a bit.

@dave sry to hear that, I'm not much help. Try Clearing your browser cache, , try a different machine or try a different browser.

[Ganado]

New topic posting is always buggy; preview hasn't worked for years. You just have to imagine the preview yourself. (And always copy your text before hitting submit, because of other random errors that happen)