Program to check if any number entered is a prime number

[xaop]

I'm planning to design a program such that any number entered will be divided by all the numbers less than it and if any of the division gives 0 as the reminder,it is not a prime.Here is my attempt so far and iam not able to proceed after that..

#include <stdio.h>
#include <conio.h>
#include <math.h>

void main()

{long int n,i,k;

clrscr();

printf("Please enter any number.\n");
scanf("%ld" , &n);


for (i=2;i<=n-1;i=i+1)

{ k=n%i;}


if (k==0) printf("It is not a prime.\n");
else printf("It is a prime.\n");



getch();


}

[Shikhin]

Well,
You should have included the if conditions, and given a break if they were true. I have also done some more changes(which I have explained in the commments). Your end code should be like this:

#include <stdio.h>
#include <conio.h>
#include <math.h>

int main()        //dont use void, always use int

{
long int n,i,k;
int prime;

clrscr();

printf("Please enter any number.\n");
scanf("%ld" , &n);


for (i=2;i<=n/2;i=i+1)     
//i<=n/2 makes the loop run faster, and always keeps it going fine.

{
k=n%i;
if (k==0)  //number is divisble by 0
{
prime = 0;      //always use {} in conditions ; prime becomes 0
}

if (prime == 0) //checks whether prime is 0 or not
{ 
printf("The number is prime.\n"); //if the condition is tru runs this code
}
else
{
printf("The number is not prime\n");
}
getch();


}

I hope you understood.
if (problem == solved)
{
mark thread = solve;
}
else
{
what to do = reply;
}
:)

[farah up]

U can modify the code by using break statement as soon as the no. is found to b a non prime...

#include <stdio.h>
#include <conio.h>
#include <math.h>

int main()        

{
long int n,i,k;
int prime=0;

clrscr();

printf("Please enter any number.\n");
scanf("%ld" , &n);


for (i=2;i<=n/2;i=i+1)     
{
k=n%i;
if (k==0)  
{
prime = 1; 
break;     
}
}
if (prime == 1) 
{ 
printf("The number is not prime.\n"); 
}
else
{
printf("The number is prime\n");
}
getch();


}

[NP-complete]

Firstly, the two of you should have explained where the OP went wrong, before giving out your (wrong, unoptimized, non-standard, non-indented) code.

@shikhin:
your code is WRONG

A thought about optimization:
the looping can be done only up to the square root of the number. You need not go up to the half of it.

Finally, to xaop:

You were right on the fact that you have to divide and check for remainders. But you have do that inside the loop and every time you find a remainder you can safely come out of the loop and say that the number is not prime. That's what the two codes did (though the first one was wrong). And if the loop terminates without finding a remainder, the variable which you used for checking (in the examples above they used "prime" though traditionally it has been named "flag") will not be modified, and that's what is being checked n the last else.

Hope this helps.

P.S: few things about the code:
1) you have included math.h but didn't use it. Now that you know that the loop should go up to the square root of the no. put it to some good use. oh, btw calculate the square root outside the loop and store the value in a variable and then use this variable in your loop construct.
2) you need not declare i as long int. A simple int would do. (and perhaps you don't even need k)
3) always indent your code. Google for more.
4) from your code, it seems that you are using turbo c as your compiler (use of void main, including conio.h, getch). Turbo C was made for MS-DOS some 20-25 years ago. Its really antique. Try code::blocks instead.

[mahmud.2345]

The error of ur code is in line 11. First of all u didn't initialize the value of k. secondly when u are putting the mod value in k its changing the value up to the last round of the loop so in last when its not becoming the 0 then its printing its a prime number. For example if u put 121 then it will be printed that its a prime number but its not a prime number in real. but how its happening see it in the code

#include <stdio.h>
#include <conio.h>
#include <math.h>

void main()

{long int n,i,k;

clrscr();

printf("Please enter any number.\n");
scanf("%ld" , &n);


for (i=2;i<=n-1;i=i+1)

{ k=n%i;} 
             [B]/* when taking input 121 on the last loop 121 is mod by 120 and the   
             reminder is 1.0008333. so the value of k is set to 1. so at the time of
             of printing its print that its a prime number. In real its not a prime
             so please  use a loop to do it and must use a break.*/[/B]


if (k==0) printf("It is not a prime.\n");
else printf("It is a prime.\n");



getch();


}

[technology]

I came across a solution that worked for checking prime numbers. The idea is to square the input and check if the squared input of the number in question is prime if so then the input is prime and this seems to cut the loop sizes smaller when checking if a number is a prime number.

[technology]

This is short and sweet and if any problems is easily modifiable,
Not it checks the squared numbers to reduce the loop size and also
the loop starts at 3 and goes up by 2 each increment so skips even numbers.
This speeds the checking for a prime number when check larger numbers.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

//*************************************************
//skips even numbers and only checks squared values
//reduces the loop size runtime
//*************************************************
#pragma argsused

int IsPrime(long number);

int main(int argc, char *argv[]){
	long n;

   clrscr();
   printf("Enter number to check for primality:");
   scanf("%ld",&n);
	if(IsPrime(n)) {
   	printf("Number is a prime\n");
   } else {
      printf("Number is not a prime\n");
   }

   int c;
   printf("Press any key to continue..");
   c = getch();
}

int IsPrime(long number) {
    long i;
    if(number == 1 || number == 3) {
    	return 1;
    }
    if (number == 2) {
    	return 0;
    }
    for (i=3; (i*i)<=number; i+=2) {
        if (number % i == 0) return 0;
    }
    return 1;
}

[technology]

The above post solves the thread

[technology]

forgot needed to check munber 2 Solution provided is solution to question. So Flag as solved.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

//*************************************************
//skips even numbers and only checks squared values
//reduces the loop size runtime
//*************************************************

int IsPrime(long number);

int main(int argc, char *argv[]){
	long n;
   printf("Enter number to check for primality:");
   scanf("%ld",&n);
	if(IsPrime(n)) {
   	printf("Number is a prime\n");
   } else {
      printf("Number is not a prime\n");
   }

   int c;
   printf("Press any key to continue..");
   c = getch();
}

int IsPrime(long number) {
    long i;


    for (i=3; (i*i)<=number; i+=2) {
        if (number % i == 0) return 0;
    }
    return 1;
}

[technology]

now checks number 2, the code works by only showing a failure if the division by number 2 works or on an even number this is how the code manages to check for non prime numbers, if the check for number 2 is taken out then all results return true for prime numbers.

The check for positive odd prime numbers only checks 3 5 7 9 11 ... upto n

so Ive check this and the code works so solved.

Sorry for earlier code without the check for value 2 for non primes.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

//*************************************************
//skips even numbers and only checks squared values
//reduces the loop size runtime
//*************************************************

int IsPrime(long number);

int main(int argc, char *argv[]){
	long n;
   printf("Enter number to check for primality:");
   scanf("%ld",&n);
	if(IsPrime(n)) {
   	printf("Number is a prime\n");
   } else {
      printf("Number is not a prime\n");
   }

   int c;
   printf("Press any key to continue..");
   c = getch();
}

int IsPrime(long number) {
    long i;



    i =2;
    if (number % i == 0) return 0;
    
    for (i=3; (i*i)<=number; i+=2) {
        if (number % i == 0) return 0;
    }
    return 1;
}