Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    2
    ReputationRep:
    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?
    Offline

    13
    ReputationRep:
    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
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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
    Offline

    13
    ReputationRep:
    it is yh. Come to think about it I cant believe that it hasn't popped up before
    Offline

    17
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    KYS you egg
    Offline

    17
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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
 
 
 
  • 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.

  • Poll
    Did TEF Bronze Award affect your UCAS choices?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.