Jump to content
  • Advertisement
Sign in to follow this  
monkeyboi

Any faster way to calculate prime number?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!