Prime number program

[doom]

So I accidentally posted this is the wrong forum. Anyway, I'll post it here again because the other one should be deleted.

I need to write a program that gets an integer 'n' as input and outputs all of the odd primes less than or equal to 'n'. This is what I currently have:

#include<iostream>
using namespace std;

int main(){
  int num;
  bool prime;

  cout << "Please enter a positive integer" << endl;
  cin >> num;

  for(int i = 3; i <= num; i++){
    prime = true;
    for(int n = 2; n <= i - 1; n++){
      if(i % n == 0){
        prime = false;
      }
    }
    if(prime){
      cout << i << " is prime" << endl;
    }
  }

  return 0;
}

Now whilst this works, it runs slowly when calculating with large numbers. What I'd like to do is use some while loops and make it run more efficiently. Any help anyone could offer would be greatly appreciated.

[z05DSL3A]

Here is a faster function for prime evaluation:

#include <math.h>
bool isPrime (int num)
{
    if (num <=1)
        return false;
    else if (num == 2)         
        return true;
    else if (num % 2 == 0)
        return false;
    else
    {
        bool prime = true;
        int divisor = 3;
        double num_d = static_cast<double>(num);
        int upperLimit = static_cast<int>(sqrt(num_d) +1);
        
        while (divisor <= upperLimit)
        {
            if (num % divisor == 0)
                prime = false;
            divisor +=2;
        }
        return prime;
    }
}

...
    for(int i = 3; i <= num; i++)
    {
        if( isPrime(num) )
        {
            cout << i << " is prime" << endl;
        }
    }
...

[xabnu]

If you don't mind storing the prime numbers in an array during the calculation, you could print them all out at the end, and speed up the overall process as well. No reason to check if a number is divisible by 10 when you've already seen that it isn't divisible by 2 and 5, etc.

So store all the prime numbers you have discovered in an array, and check the next integer only with the entries in the array, and only those less than or equal to the square root of the integer you're checking.

[PoliticalDestruction]

Here is a really efficient way to check if a number is prime. I took this out of my program that is currently running to see how many prime numbers are in a googol.

Btw, I'm also trying to find someone to make this more efficient.

#include "stdafx.h"
#include <math.h>
#include <iostream>

using namespace std;
using namespace System;


int IS_prime(double num);		// Returns '0' if its prime, and a '1' if its not prime.

int IS_prime(double num)
{
	int isprime = 0;
	for(int i = 2; i <= sqrt(num); i += 2)
	{
		if(i % 2 == 0)
			i++;

		if((int(num)% i) == 0)
		{
			isprime = 1;
			break;
		}
	}

	return isprime;
}

[satm2008]

PoliticalDestruction:

First of all, I would not define a function to check a floating-point number whether it is a prime, as a prime is always an integer.
Next, I would not use down-casting for double number to int number as it would lose the actual value.
And finally, your progam is not right. Check it out with inputting a value 1234567890 which your program states is a prime number

Doom:
Here the most efficient (I could come up with) way of checking a prime number.

#include <iostream>

using namespace std;
//using namespace system;


int isPrime(long num) // Returns 1 (true) if its prime, or 0 (false) if not
{
if (num < 2) // 1 is not a prime number
return 0;

// if it is > 2 and an even number, then it definitely is not a prime
if (num > 2 && (num % 2) == 0)
return 0;

//considering the fact all can be divided by 1 and itself,
//start checking if there is any other divisor, if found one then no need to continue, it is not a prime
for(int i = 2; i < num; i++ )
{
cout << " divisor: " << i << endl;
if ( (num % i) == 0) // if it is divisible by i
{
// a divisor other than 1 and the number itself
return 0; // no need for further checking
}
}


return 1; // if all hurdles/checks are crossed, heyyyy, its a prime
}

int main()
{
int num;
do {
cout << " enter a number (0 to stop) " << endl;
cin >> num;
if (num) {
if (isPrime(num))
cout << num << " is a prime numebr " << endl;
else
cout << num << " is NOT a prime numebr " << endl;
}
} while (num > 0);

return 0;
}


This one loops utmost 9 times to check if any given number is a prime.
Any number should come out with a divisor 1 to 9 (I guess any number).
Hence the maximum number of iterations it takes to check if given number is a prime, is 9 times.

I guess that is most efficient and quickest loop to check.

Good luck :)

[xabnu]

Is that not what doom had to begin with, only more complilcated?

I sort of doubt doom is looking anymore, but this is what i meant (and i think it beats all of those):

#include<iostream>
#include<cstdlib>
using namespace std;

int main(){
  int num, numprimes = 1;
  int *primes,*temp; // i'm not sure if temp will be necessary to prevent memory leaks maybe someone could tell me
  bool prime;

  primes = (int*)malloc(1*sizeof(int));
  primes[0] = 2;

  cout << "Please enter a positive integer" << endl;
  cin >> num;

  for(int i = 3; i <= num; i++){
    prime = true;
    for(int n = 0; n < numprimes; n++){
      if(i % primes[n] == 0){  /* if it is divisible by a compound number, then it was definitely divisible by a lesser prime. 
                                  why bother with compounds? */
        prime = false;
        break;                    // this might also speed things up
      }
    }
    if(prime){
      cout << i << " is prime" << endl;
      temp = (int*)realloc(primes,(++numprimes)*sizeof(int));
      if(temp != primes) free(primes);
      primes = temp;
      primes[numprimes-1] = i;
    }
  }

  return 0;
}

This one might take longer to find all the primes below the input for smaller inputs, but for greater inputs, it will be much faster. For really large numbers you might want to write them to a file. If you think this is fast enough, as i do, then you may leave out the bit about square roots; sqrt() itself isn't so fast a function. But then, for REALLY large numbers, it may be useful.

[msram]

The fastest method to check for primality discovered so far is the AKS algorithm. Please see the paper "PRIMES in P" at http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf for the actual algorithm with its correctness proof and http://islab.oregonstate.edu/koc/ece575/04Project2/Halim-Chanleudfa/Report.pdf for an implementation of the same in C.

Some introductory notes for this work may be found at http://mathworld.wolfram.com/news/2002-08-07/primetest/