20050102, 17:15  #1 
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)?

20050102, 19:02  #2  
Bamboozled!
May 2003
Down not across
2^{3}×3^{3}×47 Posts 
Quote:
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 

20050102, 19:29  #3 
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))... 
20050102, 19:34  #4 
Nov 2004
UK
2×19 Posts 
My error folks  sorry for the darn silly question

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Accuracy and Precision  davieddy  Math  0  20110314 22:54 
computer accuracy  lfm  Puzzles  34  20091110 15:41 
CPU Credit Accuracy  g0vegan  PrimeNet  1  20081104 20:26 
Verify Accuracy of Test  Numbers  PrimeNet  8  20050731 08:16 
Accuracy of our work [k*2^n1, k<300]  Kosmaj  15k Search  87  20041113 09:35 