Click here to Skip to main content
12,759,704 members (32,201 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

C

Stats

28.9K views
109 downloads
7 bookmarked
Posted 10 Jun 2010

Quicker Prime Number Test

, 11 Feb 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Anshul R
Student
India India
No Biography provided

You may also be interested in...

Pro
Pro

Comments and Discussions

 
GeneralMy 5 Pin
Manish K. Agarwal2-May-13 23:49
memberManish K. Agarwal2-May-13 23:49 
QuestionValidity of formula Pin
LWessels21-Aug-12 5:59
memberLWessels21-Aug-12 5:59 
AnswerRe: Validity of formula Pin
pranav9525-Sep-12 4:24
memberpranav9525-Sep-12 4:24 
GeneralMy vote of 5 Pin
pasztorpisti12-Aug-12 23:59
memberpasztorpisti12-Aug-12 23:59 
QuestionGood One Pin
Chandrasekharan P7-Mar-12 23:11
memberChandrasekharan P7-Mar-12 23:11 
Generalawesome... Pin
kr_harsha16-Feb-12 5:53
memberkr_harsha16-Feb-12 5:53 
GeneralReason for my vote of 5 I did not knew the 6k 1 or 6k-1 rule... Pin
frobertrti23-Jan-12 15:01
memberfrobertrti23-Jan-12 15:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170217.1 | Last Updated 11 Feb 2012
Article Copyright 2010 by Anshul R
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid