11,926,472 members (54,829 online)
alternative version

27K views
7 bookmarked
Posted

# Quicker Prime Number Test

, 11 Feb 2012 CPOL
 Rate this:
Prime Number Testing

## Introduction

I've tried to harness C's speed and an efficient algorithm for prime number testing.

## Background

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.

## Explanation

The two facts I just mentioned are converted to code here.

```#include <stdio.h>
#include <math.h>
main()
{
unsigned long int testno;
unsigned long int i=0;
unsigned long int testsqrt;
printf("Enter number for checking : \n");
scanf("%lu",&testno);
if(testno==2||testno==3){
printf("\nPrime");
getch();
exit();}
if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0))
{
testsqrt=ceil(sqrt(testno));
for(i=5;i<=testsqrt;i++)
{
if(i%2==0||i%3==0)
continue;
if(testno%i==0)
{
printf("\nNot Prime");
getch();
exit();
}
}
}
else
{
printf("\nNot Prime");
getch();
exit();
}
printf("\nPrime");
getch();
}```

First, it checks if the number is 2 or 3 and if it is one of them, it prints that the number is prime.

The line:

`if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0))`

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 `"Not Prime"`.

Then, `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 `"Not Prime"`.

If no number divides `testno`, finally, the program prints that the number is prime and exits.

## Share

 Student India
No Biography provided

## You may also be interested in...

 First Prev Next
 My 5 Manish K. Agarwal2-May-13 23:49 Manish K. Agarwal 2-May-13 23:49
 Validity of formula LWessels21-Aug-12 5:59 LWessels 21-Aug-12 5:59
 Re: Validity of formula pranav9525-Sep-12 4:24 pranav95 25-Sep-12 4:24
 My vote of 5 pasztorpisti12-Aug-12 23:59 pasztorpisti 12-Aug-12 23:59
 Good One Chandrasekharan P7-Mar-12 23:11 Chandrasekharan P 7-Mar-12 23:11
 awesome... kr_harsha16-Feb-12 5:53 kr_harsha 16-Feb-12 5:53
 Reason for my vote of 5 I did not knew the 6k 1 or 6k-1 rule... frobertrti23-Jan-12 15:01 frobertrti 23-Jan-12 15:01
 Last Visit: 31-Dec-99 19:00     Last Update: 27-Nov-15 3:12 Refresh 1