Primes

mathkid9

New member
Joined
Oct 16, 2009
Messages
8
I've been spending the last week or so trying to learn more about primes. One of the things I've done so far is to create a computer program which calculates the primes from 1 to any number and writes them to a text file. One of the things I would like the program to be able to do is to make an approximation of how long it should take to run all of the calculations. I've already done a basic approximation of how many primes there should be by NumOfPrimes=TopNum/Ln(TopNum/3). It usually over guesses by .1%, which is pretty good. Unfortunately because there is no algorithm which returns every prime, i had to write my own. It's not great, and one of the set backs is that the higher it goes, the slower it runs. So it takes significantly longer to compute if 1 million is a prime than it does to determine if 50,000 is. So, i ran through the program a few times, and created a spread sheet which shows how high the program computes to, how many primes there are under that number, how long it took the computer to do the calculations, and total number of calculations done. Obviously the time it took the computer to do the number of calculations depends on the other applications the computer is running at the time, but by running it a few times and doing averages I think my figures should be fairly accurate. By the nature of primes, the correlation between top number and time or number of calculations isn't linear. I've tried natural log regressions, power regressions, basically everything I can think of, and nothing seems to work. I'll add the spreadsheet so you guys can try your own methods of finding correlation. Any help would be extremely appreciated.
Sorry about the format, i couldnt figure out how to upload the spreadsheet since it wont let me upload excel or .txt files.

Top Number............Number of Primes.....Time to Calculate (ms)........Number of Calculations
1,000....................168.......................2.................................2,946
5,000....................669.......................12................................19,525
10,000...................1,229.....................19................................44,850
15,000...................1,754.....................29................................73,477
20,000...................2,262.....................147..............................103,856
40,000...................4,203.....................162...............................241,913
50,000...................5,133.....................237...............................318,235
75,000...................7,393.....................345...............................525,650
100,000..................9,592.....................421...............................753,145
125,000..................11,734....................494...............................993,817
150,000..................13,848....................572...............................1,248,402
200,000..................17,984....................789...............................1,791,943
300,000..................25,997....................1,119.............................2,994,819
500,000..................41,538....................1,763.............................5,747,200
750,000..................60,238....................2,603.............................9,664,341
1,000,000................78,498....................3,465.............................13,999,952
1,500,000................114,155...................5,371.............................23,698,487
2,000,000................148,933...................7,396.............................34,456,973
3,000,000................216,816...................11,334............................58,569,670
5,000,000................348,513...................19,257............................114,569,086
10,000,000...............664,579...................39,831............................286,766,654
15,000,000...............970,740...................62,393............................491,811,388
20,000,000...............1,270,607.................85,750............................722,735,268
25,000,000...............1,565,927.................110,497...........................974,278,973
40,000,000...............2,433,654.................191,525...........................1,832,247,969
 
mathkid9 said:
Obviously the time it took the computer to do the number of calculations depends on the other applications the computer is running at the time, but by running it a few times and doing averages I think my figures should be fairly accurate.
"Thinking" something is accurate has no place in mathematics.

The number of primes that you show at each break is correct.
You show 192 seconds as time for 40 million;
I ran this using Ubasic (function PRMDIV(n)=n) : 37 seconds.
So takes your program 6 times longer.

Impossible to "comment" any further...
 
I'm relatively new to programming, but that probably is because you used a precreated function, where as i wrote my own algorithm. There's is probably far more condenced, requires far fewer calculations, has optimized code, run its code more efficently, and probably some more things that i dont even know about. but my question was not asking for a critique of my programming skill, it was asking for advice on going about finding regression equations to model the results i have obtained. i've had several ideas on how to do this, but every time i try to take it any further than the first few steps of logic i get hit with the fact that there is no existing formula which returns all primes, meaning that it is difficult to determine how fast the function is growing. if you have something more constructive to say than "you suck at programming", i would love to hear it.
 
Denis said:
"Thinking" something is accurate has no place in mathematics.

Oh yeah, and just saying, some of the most brilliant work ever done in mathematics went unproven for thousands of years. The Pythagorean Theorem is used all the time, but it took decades of brilliant men before it was proven, and it was one of the largest disputes in the history of Greek math. The divide between basic algebra and geometry based schools almost went to war over people thinking that a^2+b^2=c^2 was accurate. The proof also used the sqrt(2) which was another huge divide in the world of math. The Pythagorean Theorem doesnt hold true in non-Euclidean geometry, but it is a pretty good estimation. Now i'm not saying my work is anything brilliant by any standards, but without "Thinking" as you put it, there would be no mathematics at all.
 
mathkid9 said:
… if you have something more constructive to say than "you suck at programming", i would love to hear it …


If you quote people, do not put words into their mouth.

Also, drop the attitude, or get lost.

Got the message?

 
Top