You are Here: Home >< Maths

# DC's primes program watch

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?
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
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
4. it is yh. Come to think about it I cant believe that it hasn't popped up before
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.
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.
7. KYS you egg
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.
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

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 16, 2017
Today on TSR

### Edexcel C2 Core Unofficial Markscheme!

Find out how you've done here

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams