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·1,811 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 33F16 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 16:39.

Tue Sep 28 16:39:41 UTC 2021 up 67 days, 11:08, 2 users, load averages: 1.83, 1.78, 1.71

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.