TheBeast32 54

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 1,165

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 5,138

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 381

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 19

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)

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 381

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 54

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

TheBeast32 54

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 54

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 54

Thank you all for your help!!

TheBeast32 54

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

TheBeast32 54

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