View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Any faster way to calculate prime number?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

18 replies to this topic

### #1monkeyboi  Members

Posted 06 December 2012 - 11:25 AM

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?

### #2Zaoshi Kaba  Members

Posted 06 December 2012 - 11:36 AM

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

### #3SiCrane  Moderators

Posted 06 December 2012 - 11:39 AM

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.

### #4Nypyren  Members

Posted 06 December 2012 - 11:45 AM

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.

### #5Álvaro  Members

Posted 06 December 2012 - 12: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[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';
}
}


### #6hupsilardee  Members

Posted 06 December 2012 - 02: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

### #7Álvaro  Members

Posted 06 December 2012 - 02: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.

### #8hupsilardee  Members

Posted 06 December 2012 - 03: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.

### #9sooner123  Members

Posted 06 December 2012 - 04: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.

### #10lride  Members

Posted 06 December 2012 - 05:11 PM

More on why 1 is not a prime
http://primes.utm.edu/notes/faq/one.html
An invisible text.

Posted 06 December 2012 - 05:11 PM

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, 06 December 2012 - 05:14 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #12Álvaro  Members

Posted 06 December 2012 - 05:47 PM

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)?

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

### #13Álvaro  Members

Posted 06 December 2012 - 06:07 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.

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 Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

### #14DpakoH  Members

Posted 07 December 2012 - 01:55 AM

As the Spanish expression goes, you are teaching your father how to make babies.

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

### #15sooner123  Members

Posted 07 December 2012 - 02:42 AM

I didn't "hear" a definition of prime

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.

(Fundamental Theorem of Algebra)

Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.

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.

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.

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 Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

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, 07 December 2012 - 02:50 AM.

### #16Álvaro  Members

Posted 07 December 2012 - 03:48 AM

I didn't "hear" a definition of prime

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.

Sorry if I misinterpreted what you were saying.

(Fundamental Theorem of Algebra)

Actually it's the Fundamental Theorem of Arithmetic, which is what I was referring to. The Fundamental Theorem of Algebra is something very different.

Ooops! That's exactly right.

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.

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.

Can you point at a reference that defines prime in terms of the fundamental theorem of arithmetic?

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 Wilson's theorem. There are also theorems that need to exclude 2 (example), but that doesn't mean that 2 isn't prime.

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.

It is very much related to what we are talking about. From Wikipedia:

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]

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:

In the 19th century however, many mathematicians did consider the number 1 a prime.

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.

### #17vdaras  Members

Posted 07 December 2012 - 07:29 AM

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, 07 December 2012 - 07:30 AM.

### #18Álvaro  Members

Posted 07 December 2012 - 08:09 AM

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.

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.

### #19BCullis  Members

Posted 07 December 2012 - 10:40 AM

Along with using a sieve:

http://en.wikipedia....l_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.

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.

Hazard Pay :: FPS/RTS in SharpDX (gathering dust, retained for... historical purposes)
DeviantArt :: Because right-brain needs love too (also pretty neglected these days)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.