search

lvkun / lk-demo

demo code for interesting problem
1 stars 0 forks source link

Algorithm in Problem05.py is not so efficient #1

Open pngisnotgif opened 12 years ago

pngisnotgif commented 12 years ago

Algorithm in Problem05.py is not so efficient as we can test a prime number for every second integral. Another more efficient way is test every prime number range from 2 to sqrt(n).

lvkun commented 12 years ago

Not fully understand. Could you send your version?

pngisnotgif commented 12 years ago

In Problem05.py Line 16 to 18.

To test whether a number is a prime:

  1. test N % 2;
  2. test N % {3, 5, 7, 9 ... sqrt(N) }; This can improve your speed (Yours is from 2 to (N-1) ).

O(N)--->O( (sqrt(N)/2 )