Public Group

# Any faster way to calculate prime number?

This topic is 2200 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

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

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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'; } } 

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites

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.

##### Share on other sites
More on why 1 is not a prime
http://primes.utm.edu/notes/faq/one.html

1. 1
2. 2
Rutin
22
3. 3
4. 4
khawk
14
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013643
×