|
2005-01-02, 17:15
|
#1 |
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 | |
|
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
101010000111002 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 |
|
|
|
|
|
2005-01-02, 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))... |
|
|
|
|
2005-01-02, 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 | 2011-03-14 22:54 |
| computer accuracy | lfm | Puzzles | 34 | 2009-11-10 15:41 |
| CPU Credit Accuracy | g0vegan | PrimeNet | 1 | 2008-11-04 20:26 |
| Verify Accuracy of Test | Numbers | PrimeNet | 8 | 2005-07-31 08:16 |
| Accuracy of our work [k*2^n-1, k<300] | Kosmaj | 15k Search | 87 | 2004-11-13 09:35 |
