mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-01-02, 17:15   #1
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

468 Posts
Default 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)?
amcfarlane is offline   Reply With Quote
Old 2005-01-02, 19:02   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

11·919 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-01-02, 19:29   #3
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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))...
Mystwalker is offline   Reply With Quote
Old 2005-01-02, 19:34   #4
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

2·19 Posts
Default

My error folks - sorry for the darn silly question
amcfarlane is offline   Reply With Quote
Reply

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.