- The algorithm can be improved further by observing that all primes are of the form 6m ± 1, with the exception of 2 and 3.
- This is because all integers can be expressed as (6m + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6m + 0), (6m + 2), (6m + 4); and 3 divides (6m + 3).
- So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6m ± 1 ≤ √n(sqrt(n)).
- This is 3 times as fast as testing all m up to √n.
int CheckPrime(unsigned int number) { if (number <= 3 && number > 1) return 1; // as 2 and 3 are prime else if (number%2==0 || number%3==0) return 0; // check if number is divisible by 2 or 3 else { unsigned int i; for (i=5; i*i<=number; i+=6) { if (number % i == 0 || number%(i + 2) == 0) return 0; } return 1; } }
- This code is written in C, in java we don't have unsigned keyword(however in java 8 it is included).
Sometimes the only way to move forward is to revisit the things in your past that were holding you back. You have to deal with them head on, no matter how scary they may be. Because once we do, you'll see that you can go further than you ever imagined. सो जाएँगे कल लिपटकर तिरंगे के साथ अलमारी में... देशभक्ति है साहब.... तारीखों पर जागती है। The only way out is through.
Sunday, 22 May 2016
An editorial on function to find the prime number with least time complexity :)
Labels:
C,
Time Complexity
Subscribe to:
Post Comments (Atom)
ohh nice observation ..."all primes are of the form 6m ± 1, with the exception of 2 and 3"
ReplyDelete