# DC's primes programWatch

Announcements
#1
I'm currently doing A Level Maths, and the other day I had a thought about prime numbers. I believe I have found a way to estimate with fairly high accuracy time the number of primes in a given range, using known primes up to some value. I also wrote two programs in Java with algorithms to actually do this, and after some looking I have found some interesting patterns.

If you would like to take a look, I'm currently hosting a mini write up at http://primes.esy.es/ and you can download the programs there too. If you don't trust it, there are also source files for you to compile yourself EDIT: Title got changed ;_; how do I change it?
3
2 years ago
#2
Could I just say that you're website is actually really cool. For that reason and also because youre smart im giving you a rep 1
#3
(Original post by Hajra Momoniat)
Could I just say that you're website is actually really cool. For that reason and also because youre smart im giving you a rep thanks xD
and fundamentally it's a really simple concept
0
2 years ago
#4
it is yh. Come to think about it I cant believe that it hasn't popped up before
0
2 years ago
#5
(Original post by ketchupcoke)
Hi, I'm currently doing A Level Maths, and the other day after school I had a thought about prime numbers. I believe I have found a way to estimate with high accuracy and in linear time the number of primes in a given range, using known primes up to some value.
What do you mean by linear time?

IIRC, using the standard sieve to find all the primes up to n takes time O(n log log n) so only barely slower than linear time.

There are more complex methods of finding that can evaluate pi(n) in O(n^2/3) or even .

Note that these are all *exact* methods, not approximations.
0
#6
(Original post by DFranklin)
What do you mean by linear time?

IIRC, using the standard sieve to find all the primes up to n takes time O(n log log n) so only barely slower than linear time.

There are more complex methods of finding that can evaluate pi(n) in O(n^2/3) or even .

Note that these are all *exact* methods, not approximations.
Well this assumes primes up to n are known and gives an approximation of the number of primes up to n^2. I assumed the sieve and then a simple multiplication to be linear time, but I have not studied complexity theory, so that was my mistake. It can also find a search range for the n+kth prime up to n^2.

I've also found that the sequence of differences between numbers that have the nth prime Pn as a factor and no primes < Pn repeats after a set amount of times, which somehow links to euler's phi function.
0
2 years ago
#7
KYS you egg
0
2 years ago
#8
(Original post by ketchupcoke)
Well this assumes primes up to n are known and gives an approximation of the number of primes up to n^2. I assumed the sieve and then a simple multiplication to be linear time, but I have not studied complexity theory, so that was my mistake. It can also find a search range for the n+kth prime up to n^2.
My actual point is that when you say "this algorithm is linear", the missing information is "linear in what"?

For example, everyone got very excited when we found a primality testing algorithm of "polynomial complexity". But it's obvious that given a number n we can test if n is prime in O(n) time:

loop k from 2 to n
{
if (k divides n)
return "n is composite"
}
return "n is prime".

So, if we have a trivial linear test, why was polynomial complexity a big thing? Because the complexity is polynomial in the number of digits in n, which is a much bigger deal.

So here, you said it was linear, and my immediate reaction is "it's really not hard to find the number of primes < N in O(N) time". But it appears that what you actually meant (but never said) is "I can find (approximately) the number of primes < N^2 in O(N) time". Which is somewhat more interesting.

Having said that, however, I have to say that the approach you have taken is a fairly well travelled path. Nothing wrong with what you've done, but it's nothing earth shattering.
0
#9
(Original post by DFranklin)
My actual point is that when you say "this algorithm is linear", the missing information is "linear in what"?

For example, everyone got very excited when we found a primality testing algorithm of "polynomial complexity". But it's obvious that given a number n we can test if n is prime in O(n) time:

loop k from 2 to n
{
if (k divides n)
return "n is composite"
}
return "n is prime".

So, if we have a trivial linear test, why was polynomial complexity a big thing? Because the complexity is polynomial in the number of digits in n, which is a much bigger deal.

So here, you said it was linear, and my immediate reaction is "it's really not hard to find the number of primes < N in O(N) time". But it appears that what you actually meant (but never said) is "I can find (approximately) the number of primes < N^2 in O(N) time". Which is somewhat more interesting.

Having said that, however, I have to say that the approach you have taken is a fairly well travelled path. Nothing wrong with what you've done, but it's nothing earth shattering.
Ah I see, that was my mistake. And this was just something I investigated out of curiosity, I know I am not the first person to think of this. Considering I will be going to university next year I thought it would be good practice :P
0
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Bournemouth University
Wed, 31 Jul '19
• Staffordshire University
Wed, 7 Aug '19
• University of Derby
Foundation Open Event Further education
Wed, 7 Aug '19

### Poll

Join the discussion

#### Are you tempted to change your firm university choice on A-level results day?

Yes, I'll try and go to a uni higher up the league tables (155)
17.63%
Yes, there is a uni that I prefer and I'll fit in better (76)
8.65%
No I am happy with my course choice (521)
59.27%
I'm using Clearing when I have my exam results (127)
14.45%