mersenneforum.org > Math Calculating sieving % accuracy
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-02, 17:15 #1 amcfarlane     Nov 2004 UK 2×19 Posts Calculating sieving % accuracy Is there a simple formula for determining what chance a positive integer N, will have of being prime after sieving out prime numbers up to sqrt(N)?
2005-01-02, 19:02   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

240318 Posts

Quote:
 Originally Posted by amcfarlane Is there a simple formula for determining what chance a positive integer N, will have of being prime after sieving out prime numbers up to sqrt(N)?
If N=1 it is not prime, so let us assume that N>1 in what follows.

If by "up to sqrt(N)" you mean "<= sqrt(N)", the probability of N being prime is unity --- it is a certainty because if N is composite, it has at least one prime factor <= sqrt(N).

If you mean "< sqrt(N)", the only possible way in which it could be composite is if N=p*p, where p is prime.

Given that this reasoning is so simple, I wonder if you meant to ask a different question?

Paul

 2005-01-02, 19:29 #3 Mystwalker     Jul 2004 Potsdam, Germany 3·277 Posts I had the same thought - it could be the case that the sqrt(N) in the question is meant for candidates, not for possible factors. So the biggest possible factor tested would be sqrt(sqrt(N))...
 2005-01-02, 19:34 #4 amcfarlane     Nov 2004 UK 2·19 Posts My error folks - sorry for the darn silly question

 Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Math 0 2011-03-14 22:54 lfm Puzzles 34 2009-11-10 15:41 g0vegan PrimeNet 1 2008-11-04 20:26 Numbers PrimeNet 8 2005-07-31 08:16 Kosmaj 15k Search 87 2004-11-13 09:35

All times are UTC. The time now is 03:54.

Wed Sep 30 03:54:07 UTC 2020 up 20 days, 1:05, 0 users, load averages: 1.50, 1.55, 1.53