Back to For Beginners

Any faster way to calculate prime number?

For Beginners

Started by monkeyboi December 06, 2012 05:25 PM

17 comments, last by BCullis 11 years, 4 months ago

monkeyboi

188

Author

December 06, 2012 05:25 PM

I am wondering if there is any fast way to calculate all the prime numbers within a given number N. Like give N = 10 it will produce 1,2,3,5,7
My version is divide only odd numbers by those already calculated prime numbers.



int n = 1000;

int half = n/2;

//At most n/2 prime numbers but when n is realy big this speculation is far from the accually size which is a waste(any way to solve it?)

int* temp = new int[half];

int count = 0;

if (n>3)

{

  count = 3;

  temp[0]=1;

  temp[1]=2;

  temp[2]=3;

  for (int x=5;x<=n;x=x+2)

  {

   int y;

   for(y =1; y<count;y++){

    if (x%temp[y] == 0)

    {

     //x is not a prime number

	 y = count+1;

	 break;

    }

   }

   if (y == count)

   {

   //x is a prime number

    temp[count] = x;

    count++;

   }

  }

}else{

  count = n;

  for (int x=0;x<n;x++)

  {

   temp[x] = x+1;

  }

}

// create another array which has the exact size as needed then delete the temp

int* p = new int[count];

for (int z = 0; z<count; z++)

{

  p[z] = temp[z];

}

delete [] temp;

Any problem with this one or any faster way?

Zaoshi Kaba

8,470

December 06, 2012 05:36 PM

You could use vector<size_t> to store primes, this way you won't need to to mess with memory allocation.

SiCrane

11,840

December 06, 2012 05:39 PM

If you're finding all the primes less than n, one simple but efficient way is to use the Sieve of Eratosthenes. If you're dong trial division a simple optimization is only dividing by up to sqrt(n) instead of n/2.

Nypyren

12,313

December 06, 2012 05:45 PM

Along with using a sieve:

http://en.wikipedia.org/wiki/Wheel_factorization

Save the results to a file once you've generated them, then you can just load the file, shove it in a set data structure and perform lookups very quickly from then on.

alvaro

21,604

December 06, 2012 06:31 PM

Here's a straight-forward implementation of the Sieve of Eratosthenes:

#include <iostream>

#include <vector>



int main() {

  unsigned long const N = 1000000;



  std::vector<bool> is_prime(N, true);

  is_prime[0] = is_prime[1] = false;

  unsigned long i;

  for (i = 2; i*i < N; ++i) {

    if (is_prime) {

	  std::cout << i << '\n';

	  for (unsigned long j = i*i; j < N; j+=i)

	    is_prime[j] = false;

    }

  }

  for (; i < N; ++i) {

    if (is_prime)

	  std::cout << i << '\n';

  }

}

hupsilardee

491

December 06, 2012 08:51 PM

Well, you could prove the Riemann Hypothesis, which is currently the most important unanswered question in mathematics

By the way, 1 is NOT a prime number. A prime number must have two divisors. 1 only has one divisor

alvaro

21,604

December 06, 2012 08:57 PM

Whether 1 is prime or not is a matter of convention, and the prevailing convention is that it is not a prime. There are multiple possible definitions of what "prime" means, and they often tell you explicitly that 1 is not a prime. See the beginning of the Wikipedia page for an example.

hupsilardee

491

December 06, 2012 09:16 PM

Yes, there is a little bit about primality of one, which then goes on to explain the very good reason behind 1 not being considered prime.

sooner123

269

December 06, 2012 10:32 PM

Whether 1 is prime or not is a matter of convention, and the prevailing convention is that it is not a prime. There are multiple possible definitions of what "prime" means, and they often tell you explicitly that 1 is not a prime. See the beginning of the Wikipedia page for an example.

This isn't really correct. 1 isn't a prime because it doesn't match the true definition of prime numbers. There is no convention about it.

The definition you've probably heard (something along the lines of "positive integer divisible only by 1 and itself, excluding 1") is a laymen's definition that simply happens to coincide with the real definition.

The real definition is that a prime number is an element of the set of numbers into which all positive integers can be factored into products of powers of, uniquely. It's a fundamental theorem in number theory. '1' clearly violates this because to factorize, say 12, you could have 1 * 2^2 * 3^1 or 1^2 * 2^2 * 3^1, or 1^3 * 2^2 * 3^1, etc. There are an infinite number of ways you can factorize something if you accept 1 as a prime number and primes are defined to make factorization unique.