DC's primes program Watch

ketchupcoke
Badges: 2
Rep:
?
#1
Report Thread starter 2 years ago
#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
reply
Hajra Momoniat
Badges: 16
Rep:
?
#2
Report 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
reply
ketchupcoke
Badges: 2
Rep:
?
#3
Report Thread starter 2 years ago
#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
reply
Hajra Momoniat
Badges: 16
Rep:
?
#4
Report 2 years ago
#4
it is yh. Come to think about it I cant believe that it hasn't popped up before
0
reply
DFranklin
Badges: 18
Rep:
?
#5
Report 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 \pi(x) that can evaluate pi(n) in O(n^2/3) or even O(n^{1/2 + \epsilon}).

Note that these are all *exact* methods, not approximations.
0
reply
ketchupcoke
Badges: 2
Rep:
?
#6
Report Thread starter 2 years ago
#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 \pi(x) that can evaluate pi(n) in O(n^2/3) or even O(n^{1/2 + \epsilon}).

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
reply
bigbadbarry
Badges: 0
Rep:
?
#7
Report 2 years ago
#7
KYS you egg
0
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 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
reply
ketchupcoke
Badges: 2
Rep:
?
#9
Report Thread starter 2 years ago
#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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

  • Bournemouth University
    Clearing Open Day Undergraduate
    Wed, 31 Jul '19
  • Staffordshire University
    Postgraduate open event - Stoke-on-Trent campus Postgraduate
    Wed, 7 Aug '19
  • University of Derby
    Foundation Open Event Further education
    Wed, 7 Aug '19

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%

Watched Threads

View All