Help me make my C++ program more efficient

GoldenBear

Banned
Mar 2, 2000
6,843
2
0
This is supposed to display all the prime numbers from the inputted start and end numbers..

What I'm doing now is basically going through each number from start to finish, and creating a loop within it to take the remainder of each divisible from 2 to half of that current number. Make sense?

Anyway here's my code.

while (num < max)
{
for (i = 2; i <= num/2; i++)
{
if (num % i == 0)
{
prime = false;
}
}
if (prime)
{
cout << num << &quot; &quot; << endl;
total++;
}
prime = true;
num++;
}
 

Ameesh

Lifer
Apr 3, 2001
23,686
0
0
to be more efficient you could pre-generate all prime numbers and put them in an array then just read the numbers from the array
 

geno

Lifer
Dec 26, 1999
25,074
4
0


<< Help me make my C++ program more efficient >>


Help me shave my back and it's a deal :D
 

Shadowedge

Senior member
Feb 25, 2000
335
0
0
Haha..pre-generate all prime numbers! :)

Do the loop from 2 to the square root of the number instead. :D

 

JesseKnows

Golden Member
Jul 7, 2000
1,980
0
76
if (num % i == 0)
{
prime = false;
break;
}

why keep checking numbers that are known to be compound?
 

br0wn

Senior member
Jun 22, 2000
572
0
0
Four suggestions:
1. in checking for prime number (inner loop), loop from 3 to the square root of num
...(instead of until num/2). If you start with input of 2, make it your special case
...to show that 2 is a prime number.
2. Still in the inner loop (same as in no 1 above), increase your loop by
...adding 2 (instead of adding 1).
3. In the inner loop, add break statement in the if statement or change your
...condition in the inner loop to ( i<=sqrt(num) &amp;&amp; prime == true )
4. in computing all prime (outer loop), increase the loop by 2 (start with odd number).
...Effectively, cutting down the loop by factor of 2 since all even number can't
...be prime number.

edit: adding one more suggestion
 

HansHurt

Platinum Member
Apr 5, 2001
2,615
0
0
Yea br0wn has it...but I have a suggestion that might simplify things....

































Like I actually know...HA! C+ isn't that a soft drink? Oh, man I kill myself.
 

Handle

Senior member
Oct 16, 1999
551
0
0


<< to be more efficient you could pre-generate all prime numbers and put them in an array then just read the numbers from the array >>


It can be quick for very small numbers (and some programs that generate prime numbers store the first few in an array), but it is not quicker when you get to the extremely large prime numbers and numbers of prime numbers.

GoldenBear, look up the &quot;Sieve of Eratosthenes&quot;--it gives a simple algorithm for finding out relatively small prime numbers.

Your method is decent, but to find out if, say, 29 is prime, your program has to check the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, and 14. However, if 29 is not divisible by 2, can it be divisible by 4? 6? 8? 10? 12? 14? That's 6 wasted operations! But there's more, if 29 is not divisble by 3, can it be divisible by 6? 9? 12? That's 3 more wasted operations. If 29 is not divisible by 5, can it be divisible by 10? Nope. You get my point. It may seem like a minor thing for a number like 29, but if I picked a number like, say, 82759, I could tell you that you are wasting tens of thousands of operations. That will make the algorithm too slow.

What you want to remember is this... to find out if a number is prime, you have to check ONLY if it is divisible by other PRIME numbers. Don't waste your time finding out if a potential prime divides evenly into a composite number because it is a waste of work... why? Because all composite numbers are a multiple of prime(s) so it is wholly unnecessary to check if 82759 is divisible by, say, 39. If it is divisible by 39, it is divisible by 3. If it isn't divisible by 3, don't bother checking 39, because I can tell you right now that it WON'T be divisible by 39.

So what you have to do is store the results of your program in an array. Add every new prime number you find into an array, containing all of the previous prime numbers. Then, for each upcoming number, use the modulus operator to test for divisibility. For example, do 82759%2, 82759%3, 82759%5, 82759%7, 82759%11, 82759%13, 82759%17, 82759%19, 82759%23, 82759%29, 82759%(all prime numbers up to 82759).

So here is some pseudocode (sorry, couldn't be bothered with C++ syntax--and pretend the <> are [] because it turns it into italics with the []):

//////////////////////////////////////////////////////

while(++num<max) {
--for(int i=0;i<=NumberOfElementsInArrayOfPrimes;i++) {
----if( !( num%ArrayOfPrimes<i> ) ) {
------Print num
------Add num to ArrayOfPrimes
----}
--}
}

//////////////////////////////////////////////////////

Hope this helps.

Edit: Code issues.