Any faster way to calculate prime number?

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.
[CODE]
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;
[/CODE]

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 [url=http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes]Sieve of Eratosthenes[/url]. 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:

[url="http://en.wikipedia.org/wiki/Wheel_factorization"]http://en.wikipedia.org/wiki/Wheel_factorization[/url]

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:

[code]#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[i]) {
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[i])
std::cout << i << '\n';
}
}
[/code]

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
[quote name='Álvaro' timestamp='1354827471' post='5007874']
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.
[/quote]

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

Share on other sites
Not sure if there are infinitely many ways to factorise 12 in the integers ;)

I can't remember the general definition of a prime numer, but I think it may be

a is prime => if a divides b*c then a = b or a = c

Otherwise, something to do with units (which are invertible elements with respect to multiplication, so those are +1 and -1 for the integers).

EDIT: Yeah, if a is prime and a = b * c then b or c is a unit (invertible element)? Edited by Paradigm Shifter

Share on other sites
Not sure if there are infinitely many ways to factorise 12 in the integers ;)

I can't remember the general definition of a prime numer, but I think it may be

a is prime => if a divides b*c then a = b or a = c

Otherwise, something to do with units (which are invertible elements with respect to multiplication, so those are +1 and -1 for the integers).

EDIT: Yeah, if a is prime and a = b * c then b or c is a unit (invertible element)?
[/quote]

Also, if a is a prime and a divides b*c, then a divides b or a divides c.

Share on other sites
[quote name='sooner123' timestamp='1354833160' post='5007906']
[quote name='Álvaro' timestamp='1354827471' post='5007874']
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.
[/quote]
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.
[/quote]
As the Spanish expression goes, you are teaching your father how to make babies. I didn't "hear" a definition of prime: I spent 7 years of my life becoming a mathematician, which is what I do for a living, and that involved learning a whole lot of things about primes.

The definition of prime has changed over the centuries, and so has the primality of 1. The fact that natural numbers can be decomposed into a product of primes in a unique manner is a theorem (Fundamental Theorem of Algebra) and not a definition. The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.

If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see [url="http://en.wikipedia.org/wiki/Wilson"]Wilson's theorem[/url]. There are also theorems that need to exclude 2 ([url="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test"]example[/url]), but that doesn't mean that 2 isn't prime.

Share on other sites
[quote name='Álvaro' timestamp='1354838822' post='5007937']
As the Spanish expression goes, you are teaching your father how to make babies.
[/quote]
This proverb is valid all around the world, also I can second what Alvaro said event though I don't deal directly with math for a living. Plus on this forum Alvaro is on my list of people who you should listen to, if you are smart he should be on your list too

Share on other sites
[quote name='Álvaro' timestamp='1354838822' post='5007937']I didn't "hear" a definition of prime[/quote]
I think you're mincing words here. I wasn't implying you were a layman to mathematics. Just that the definition you might have been basing that statement on was a laymen's definition. I know, from years of experience dealing with you that you have an awesome grasp of mathematics and computer science. And probably much more.

[quote name='Álvaro' timestamp='1354838822' post='5007937'](Fundamental Theorem of Algebra)[/quote]
Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.

[quote name='Álvaro' timestamp='1354838822' post='5007937']The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.[/quote]
Except that this modern definition, with which I'm familiar, is a consequence of its equivalence to the definition that satisfies the fundamental theorem of arithmetic and a desire to merge abstract algebra with number theory.

[quote name='Álvaro' timestamp='1354838822' post='5007937']If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see [url="http://en.wikipedia.org/wiki/Wilson"]Wilson's theorem[/url]. There are also theorems that need to exclude 2 ([url="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test"]example[/url]), but that doesn't mean that 2 isn't prime.
[/quote]
Yep. But this isn't really related to what we're talking about, which is the definition and whether 1's exclusion is a convention or a consequence of something deeper. Not the consequences of things being different. Edited by sooner123

Share on other sites
[quote name='sooner123' timestamp='1354869747' post='5008048']
[quote name='Álvaro' timestamp='1354838822' post='5007937']I didn't "hear" a definition of prime[/quote]
I think you're mincing words here. I wasn't implying you were a layman to mathematics. Just that the definition you might have been basing that statement on was a laymen's definition. I know, from years of experience dealing with you that you have an awesome grasp of mathematics and computer science. And probably much more.[/quote]
Sorry if I misinterpreted what you were saying.

[quote][quote name='Álvaro' timestamp='1354838822' post='5007937'](Fundamental Theorem of Algebra)[/quote]
Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.[/quote]
Ooops! That's exactly right.

[quote][quote name='Álvaro' timestamp='1354838822' post='5007937']The modern definition of prime is an element of a commutative ring that is not 0, not a unit and generates a prime ideal (that's the condition I just described in my previous post). The "not a unit" excludes 1. But this is a convention that people have found convenient, and has no deeper meaning.[/quote]
Except that this modern definition, with which I'm familiar, is a consequence of its equivalence to the definition that satisfies the fundamental theorem of arithmetic and a desire to merge abstract algebra with number theory.[/quote]
Can you point at a reference that defines prime in terms of the fundamental theorem of arithmetic?

[quote][quote name='Álvaro' timestamp='1354838822' post='5007937']If we were to consider 1 a prime, many theorems would have to be reworded to exclude it. But some other theorems would be simplified. For instance, see [url="http://en.wikipedia.org/wiki/Wilson"]Wilson's theorem[/url]. There are also theorems that need to exclude 2 ([url="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test"]example[/url]), but that doesn't mean that 2 isn't prime.
[/quote]
Yep. But this isn't really related to what we're talking about, which is the definition and whether 1's exclusion is a convention or a consequence of something deeper. Not the consequences of things being different.
[/quote]

It is very much related to what we are talking about. From Wikipedia:
[quote]Most early Greeks did not even consider 1 to be a number,[4] so did not consider it a prime. In the 19th century however, many mathematicians did consider the number 1 a prime. For example, Derrick Norman Lehmer's list of primes up to 10,006,721, reprinted as late as 1956,[5] started with 1 as its first prime.[6] Henri Lebesgue is said to be the last professional mathematician to call 1 prime.[7] Although a large body of mathematical work is also valid when calling 1 a prime, the above fundamental theorem of arithmetic does not hold as stated. For example, the number 15 can be factored as 3 · 5 or 1 · 3 · 5. If 1 were admitted as a prime, these two presentations would be considered different factorizations of 15 into prime numbers, so the statement of that theorem would have to be modified. Furthermore, the prime numbers have several properties that the number 1 lacks, such as the relationship of the number to its corresponding value of Euler's totient function or the sum of divisors function.[8][9][/quote]

As you see, the justification for not considering 1 a prime precisely has to do with the fact that many theorems would have to make exceptions for 1.

This quote alone supports my claim that 1 not being a prime is pure convention:
[quote]In the 19th century however, many mathematicians did consider the number 1 a prime.[/quote]
It's not like they made a mistake by considering 1 a prime: They simply used a different convention. I am not saying that all conventions are equally valid: There are valid reasons to prefer the current one. But thinking that the convention is a consequence of the definition and not the other way around is the wrong way to look at it.

Share on other sites
On a side note, if an integer can't be divided by 2 then it also can't be divided by any other even number, so you can try 2 and then only try odd numbers from 3 to sqrt(x), where x the integer that you check for primality. Edited by vdaras

Share on other sites
[quote name='vdaras' timestamp='1354886948' post='5008109']
On a side note, if an integer can't be divided by 2 then it also can't be divided by any other even number, so you can try 2 and then only try odd numbers from 3 to sqrt(x), where x the integer that you check for primality.
[/quote]

Yes, you can also check 2 and 3 first, and then you only need to check division by multiplies of 6 plus 1 and multiples of 6 minus 1. That's usually how I implement trial division.

If you want to test larger numbers, you probably want to use the probabilistic Miller-Rabin test.

Share on other sites
[quote name='Nypyren' timestamp='1354815918' post='5007825']
Along with using a sieve:

[url="http://en.wikipedia.org/wiki/Wheel_factorization"]http://en.wikipedia....l_factorization[/url]

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.
[/quote]

Even quicker: find a published source of primes and reference that! (partially joking). When I solved this for the Euler project, I just referenced the Prime Pages. It's meta-programming, in that I leveraged the storage lookup table created by the human species. But writing an implementation of a Sieve yourself is still great practice.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628277
• Total Posts
2981776

• 10
• 11
• 17
• 11
• 9