 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 468 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

11·919 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   Thread Tools Show Printable Version Email this Page 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 09:12.

Tue Oct 20 09:12:06 UTC 2020 up 40 days, 6:23, 0 users, load averages: 1.53, 1.76, 1.71