Prime Number Generator slow

[TheBeast32]

I have been making a prime number generator.
It works, but it's considerably slow if a user enters a high number. If anyone has any suggestions on how to make it faster, please post it.

Here's the genrator code:

unsigned long int theNumber;
unsigned long int Factor1 = 1, Factor2 = 1;

//-----------Find the prime number-----------------
  do
  {
  Factor2 = 1;
  Factor1 += 1;
  
  if (Factor1 * Factor2 != theNumber)
  {
  isPrime = FALSE;
  } // End if
  else
  {
  isPrime = TRUE;
  } // End else
  
  while (Factor1 < (theNumber / 2) + 1 && Factor2 < theNumber && Factor1 * Factor2 != theNumber)
  {
  Factor2++;
  
  if (Factor1 * Factor2 != theNumber)
  {
  isPrime = FALSE;
  } // End if
  else
  {
  isPrime = TRUE;
  } // End else
  
  } // End while
  } while (Factor1 * Factor2 != theNumber); // End do
  //-------------------Done finding------------------
  
  // Display the results
  switch (isPrime)
  {
  case TRUE:
  cout << "\n Hurray! It's a Prime Number!";
  break;
  
  case FALSE:
  cout << "\n Sorry, It's Not a Prime Number.\nThe two factors we found were: " << Factor1 << " and " << Factor2 << ".";
  break;
  } // End switch

[vmanes]

A complete program would make it easier to evaluate your code.

What you present does not seem to be a prime generator (something which will list out the primes in a given range) but rather, a tester for a given input number - is this prime or not.

And at that, it appears to not work - it tells me every number is prime.

In testing for primeness in a brute force way like this, you only need one factor to consider. Does this number divide evenly into the value being tested? If at any time, up to value/2, you get an even division, you have a non-prime value.

Search this forum and you'll find many discussions and samples of prime number code.

[Salem]

Also learn how to indent your code. It's much easier to follow the logic of your program that way (for you and for us).

[invisal]

Why make your code so complicated? The most basic concept of finding prime is to test from 2 until number-1. Once you find the divisor number of that number, then you are also able to find the factor of that number.

int factor1, factor2;
    bool prime = true;
    for(int i=2; i<num; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

To improve the proformence speed, you don't need to test from 2 to number-1; you can simply test it until number/2

bool prime = true;
    temp = num/2;
    for(int i=2; i<=temp; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

To improve even more proformence speed, you can test it only test it until sqrt(number).

bool prime = true;
    temp = sqrt(temp);
    for(int i=2; i<=temp; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

[Karkaroff]

u can make it faster by incrementing counter by 2 when divisibilty by 2 fails.

u can further accelerate, by avoiding checking multiples of numbers already checked.(sieve of Eratosthenes)

Read sth about it at
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
also,
http://en.wikipedia.org/wiki/Primality_test
will help.

and...
personally, i feel checking till n/2 will be more efficient than sqrt(n). because sqrt(n) may take more steps.

u can also update the upper limit during each iteration
as
for (i=3;i<=n/i;i++)

[invisal]

u can make it faster by incrementing counter by 2 when divisibilty
personally, i feel checking till n/2 will be more efficient than sqrt(n). because sqrt(n) may

It depends; the bigger the number is, the faster the running till sqrt(n) perform. Another thing, all the prime number, except number 2 and 3, are in this format 6k+1 or 6k-1; however, not all the 6k+1 or 6k-1 are prime number. In this case, you can increase by 6 if you want to speed up.

Note: (Shamefully to say, but I just found out that all my example codes were mising one close brace)

[TheBeast32]

Thanks, and sorry for getting back so long, I had to go.

[TheBeast32]

Why make your code so complicated? The most basic concept of finding prime is to test from 2 until number-1. Once you find the divisor number of that number, then you are also able to find the factor of that number.

int factor1, factor2;
    bool prime = true;
    for(int i=2; i<num; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

To improve the proformence speed, you don't need to test from 2 to number-1; you can simply test it until number/2

bool prime = true;
    temp = num/2;
    for(int i=2; i<=temp; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

To improve even more proformence speed, you can test it only test it until sqrt(number).

bool prime = true;
    temp = sqrt(temp);
    for(int i=2; i<=temp; i++) {
        if (num%i==0) {
            prime = false;
            factor1 = i;
            factor2 = num/i;
            break;
    }

I just tried that.
Whenever i entered an odd number, it said it was prime.....
Maybe it's just me or someting, but it didn't work

[TheBeast32]

I made my own code based on your idea though.

it's right here:

#include <iostream>
using namespace std;

int main()
{
       int factor1, factor2;    
       bool prime = true;   
       cout << "Enter a number";
       int num;
       int x=2;
       char stopchar;
       cin >> num;

while (x < (num / 2) + 1)
{
      if (num % x == 0)
      {
      prime = false;
      }
      else 
      {
      prime = true;
      }
      cout << x;
      x++;
}
switch (prime)
{
       case true:
       cout << "it's prime";
       break;
       case false:
            cout << "it's not!";
            break;
}
cin >> stopchar;
       return 32;
       }

[TheBeast32]

Thank you all for your help!!

[TheBeast32]

whoops! Mine doesn't work either!
I dont know what to do now.........

[TheBeast32]

OH!, I figured it out!!! thanks everyone, nowi got it.