Generate Prime

• I found this little gem while browsing for books at amazon. I have not verified that it actually is from the book but if it is... wow... I especially like how he verifies i%2 != 0 and i%4 != 0 just to make sure he doesnt miss those pesky odd numbers dividable by four...

generous star for that). If you've written C/C++ professionally for a
living, you wouldn't stand looking at the code snippets in this book
except some parts that's copied from the open source Quant Lib.
Furthermore, the computational errors in the book shows you how
careless the code examples are: On page 85, it has a function which is
pupported to return the smallest prime greater than or equal to N:

inline long generatePrime(long N) {

Long i = N;

bool flag = false;

do {

// check if number is prime

if( ( i%2 != 0 ) && (i%3!=0) && (i%4 != 0) && (i%5 != 0) && (i%6 != 0)

&& (i%7 != 0) && (i%8 !=0) && (i%9 != 0) )

flag = true;

else

i++;

} while ( flag != true);

return i;

}

Is this a great mathematical discovery or what? Try this function with N=121! Just don't bet any money on it!

• @Albin said:

if( ( i%2 != 0 ) && (i%3!=0) && (i%4 != 0) && (i%5 != 0) && (i%6 != 0)
&& (i%7 != 0) && (i%8 !=0) && (i%9 != 0) )
It gets every prime greater than 7 and less than 121. I guess no one told the author that 2, 3, 5 and 7 are primes.

• @Albin said:

I found this little gem while browsing for books at amazon. I have
not verified that it actually is from the book but if it is... wow... I
especially like how he verifies i%2 != 0 and i%4 != 0 just to make sure
he doesnt miss those pesky odd numbers dividable by four...

Holy fuck!!!1!  You didn't tell us the title was:

Now we know where that missing \$7b went and why the entire global economy is so screwed!

</scared now>

•

• In related news, there is a prize for the formula to generate a sequence of primes.  I specify formula, not algorithm.  I think it was originally offered by the Clay Mathematics Institute under their Millenium Prize Problems.  It seems to have either been solved, or, more likely, removed from the list.

http://www.claymath.org/millennium/

/Generating primes is not for the faint of heart.

• It seems this guy stole the code in his book that does work from OSS programs without attribution.  Most of the five-star reviews on Amazon have the stink of sockpuppet shills, too.  The guy's not only incompetent but dishonest as well.

• @CRNewsom said:

I specify formula, not algorithm.

There's no significant difference, they're just two ways of phrasing the same thing.

• @asuffield said:

@CRNewsom said:

I specify formula, not algorithm.

There's no significant difference, they're just two ways of phrasing the same thing.

The only reason I specified was to take into account the audience to whom I was speaking.  What the institute was looking for was more wooden table than a beautifully written piece of code.  The code, of course, could brute force a solution, thus, eliminating the purpose of the exercise.

• @CRNewsom said:

In related news, there is a prize for the formula to generate a sequence of primes.  I specify formula, not algorithm.  I think it was originally offered by the Clay Mathematics Institute under their Millenium Prize Problems.  It seems to have either been solved, or, more likely, removed from the list.

http://www.claymath.org/millennium/

/Generating primes is not for the faint of heart.

Only one of the Millenium Prize Problems has been solved so far, and it's to do with topology, not number theory.  And, well, generating primes is trivial provided performance is no object, and in certain special cases it's easy to do with high performance as well.

I guess you have a vague memory of the Riemann Hypothesis, since that has a connection with the distribution of primes?  But that's a much more subtle issue.

• @seaturnip said:

@CRNewsom said:

In related news, there is a prize for the formula to generate a sequence of primes.  I specify formula, not algorithm.  I think it was originally offered by the Clay Mathematics Institute under their Millenium Prize Problems.  It seems to have either been solved, or, more likely, removed from the list.

http://www.claymath.org/millennium/

/Generating primes is not for the faint of heart.

Only one of the Millenium Prize Problems has been solved so far, and it's to do with topology, not number theory.  And, well, generating primes is trivial provided performance is no object, and in certain special cases it's easy to do with high performance as well.

I guess you have a vague memory of the Riemann Hypothesis, since that has a connection with the distribution of primes?  But that's a much more subtle issue.

I agree that Riemann is the basis of the problem, however, I see much that can be done once some of the number theory subproblems (specifically primes) are solved.  Quite honestly, this is not my field of expertiese, but more of a very frustrating hobby.

• @Albin said:

Is this a great mathematical discovery or what? Try this function with N=121! Just don't bet any money on it!

Look, anyody who thinks they need to generate large prime numbers is mislead.  For any cryptographical purposes, a number need not be prime.  It only needs to be sufficiently pseudoprime.  Next you'll be expecting us to generate truly random numbers too.

• I think you forgot your sarcasm tags....

• @CRNewsom said:

I agree that Riemann is the basis of the problem, however, I see much that can be done once some of the number theory subproblems (specifically primes) are solved.  Quite honestly, this is not my field of expertiese, but more of a very frustrating hobby.

Erm, except that proving the Riemann hypothesis may be the best chance at "solving" prime numbers.

• Maybe that's the way they did it on Cybertron...

• Of course the (i%2!=0) && (i%3!=0) etc isn't the only problem, but the code is also too long. I would have done something like this:

<xmp>for(;;i++) if(isprime(i)) return i;</xmp>
Of course it won't work if isprime() isn't defined or if it doesn't do what you want it to do. The next thing to do is make a proper function to check if is prime. I think just checking all integers up to the square root of the number that you are checking will works

•  you dont even have to do that;

if you keep a list of all primes you only have to check your new number against those primes less than sqrt(n)

• @rabidgoldfish said:

...if you keep a list of all primes...
I'm certain if one already had a list of primes generating a prime would be a simple matter of reading the list. Either you misread something or didn't communicate properly. Did you mean "if you keep a list of primes you already know about"?

• @asuffield said:

@CRNewsom said:

I specify formula, not algorithm.

There's no significant difference, they're just two ways of phrasing the same thing.

What about closed form solutions vs numeric solutions though? That sounds like a pretty good equivalent to the common understanding of the words "formular" and (non-trivial) "algorithm".

• @PSWorx said:

@asuffield said:

@CRNewsom said:

I specify formula, not algorithm.

There's no significant difference, they're just two ways of phrasing the same thing.

What about closed form solutions vs numeric solutions though?

I am aware of no practical use for the classification of closed-form solutions. To the best of my knowledge, it exists only for math professors to torment undergrads, and has no actual value.

That sounds like a pretty good equivalent to the common understanding of the words "formular" and (non-trivial) "algorithm".

The thing is that, under the Church-Turing thesis, the two things referenced by the common understanding are in fact exactly equivalent. Any effectively computable algorithm or fomula can be transformed into at least one equivalent form of the other. This is one of those statements that is at the same time both very simple and very profound.

("effectively computable" excludes uninteresting nonsense like "a != a")

• Prime numbers are for sci fi movies since WTF CARRRRRRES if  a number is prime.  Get a life, Mathematicians.

• @Lysis said:

Prime numbers are for sci fi movies since WTF CARRRRRRES if  a number is prime.  Get a life, Mathematicians.

Tell that to Bruce

• Here is the code to do it in Yuri (a program language I am working on inventing):

`until({@isprime};{++})`

You could also do it like this instead if you prefer:

`{++} until({@isprime})`

Because Yuri does have a built-in @isprime function

• @zzo38 said:

a program language I am working on inventing

• Sorry, I meant

`@isprime@`
not
`@isprime`
OK after this misatke I fix, fine I stop until is finish when finish I post somewhere else not here, post here is no good you are right, post if not finish is also no good but that's OK now I learn OK.

Also tell me, is that a worst book than even that? Or is this the worst thing in that book

• @zzo38 said:

Sorry, I meant

`@isprime@`
not
`@isprime`

OK after this misatke I fix, fine I stop until is finish when finish I post somewhere else not here, post here is no good you are right, post if not finish is also no good but that's OK now I learn OK.

Also tell me, is that a worst book than even that? Or is this the worst thing in that book

oooh look! It's a chinese warcraft gold farmer!

• @Lysis said:

oooh look! It's a chinese warcraft gold farmer!

OK, fine, you are right, I looked at it some more, and now I realized this codes has to do with Chinese warcraft it doesn't have to do with prime numbers

• @zzo38 said:

@Lysis said:

oooh look! It's a chinese warcraft gold farmer!

OK, fine, you are right, I looked at it some more, and now I realized this codes has to do with Chinese warcraft it doesn't have to do with prime numbers

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.