I've tried to harness C's speed and an efficient algorithm for prime number testing.
What you need to know is 2 facts.
- If the number can be factored into two numbers, at least one of them should be less than or equal to its square root.
- Every prime number can be represented by the form 6k+1 or 6k-1.
The two facts I just mentioned are converted to code here.
unsigned long int testno;
unsigned long int i=0;
unsigned long int testsqrt;
printf("Enter number for checking : \n");
First, it checks if the number is 2 or 3 and if it is one of them, it prints that the number is prime.
filters out a majority of the non-prime numbers.
First, it tests if the number can be represented by the form 6k+1 or 6k-1 and then if it is a multiple of 2 or 3.
If it can be represented in either of the forms(6k+1 or 6k-1), then it proceeds to the checking loop.
If the condition fails, the program exits after printing
testsqrt stores the square root of
testno(the number the user inputs).
The loop counter i starts from 5 (2 and 3 have been already checked. Every multiple of 4 is divisible by 2 which has already been checked too).
Then, the counter is checked if it is even or if it is a multiple of 3. If it is either, then the program proceeds to the next iteration.
Then, the program checks if
testno is a multiple of the current number(counter).
If it is, then the program prints
If no number divides
testno, finally, the program prints that the number is prime and exits.