@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.
