http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
On Thu, May 19, 2011 at 1:47 AM, Don <[email protected]> wrote: > Yes. Use a sieve. > Don > > On May 17, 11:36 pm, wujin chen <[email protected]> wrote: > > @Daveļ¼ thanks for your reply. > > i know that, i can only check from 6*n - 1 and 6*n + 1.. > > assume that, n=10000 , and we begin from k=1667, the number needed to > check > > is 10001,10003.... > > but to determin 10001 is prime or not costs a lot, right? > > when the n is huge, it will be not feasible. > > > > is there some math principle to solve this problem easily? > > > > 2011/5/18 Dave <[email protected]> > > > > > @Wujin: Well, obviously, you don't have to check _every_ number one-by- > > > one. If n > 1, you can ignore every even number. Furthermore, if n > > > > 3, you can ignore every odd multiple of 3. That means that you need to > > > check only numbers of the form 6*n - 1 and 6*n + 1. > > > > > Dave > > > > > On May 17, 9:09 pm, wujin chen <[email protected]> wrote: > > > > given a number n, compute the smallest prime that is bigger than n. > > > > for example, n=8, then the smallest prime that bigger than 8 is 11. > > > > > > i wonder whether there is an effective way, rather than check every > > > number > > > > bigger than n one by one. > > > > > > thanks. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
