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

2×3×29×67 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 2616 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 21:35.

Wed Feb 1 21:35:52 UTC 2023 up 167 days, 19:04, 0 users, load averages: 1.02, 1.25, 1.08