Prime Number

[vinodhsml]

#include<stdio.h>
#include<conio.h>               //header file declaring
void main()
{
    int a,i;
    clrscr();
    printf("\n Enter the Number:");      //get value
    scanf("%d",&a);

    if(a%2==0) {
        printf("\n Not prime number");
    } else {
        for(i=3; i<a; i=i+2) {
            if(a%i==0) {
                printf("\n Not a prime");
                break;
            }
        }
        printf("\n Prime number");
    }
    getch();
}

[D33wakar]

Well, I compiled your code and entered the number 119 and it printed out:
" not a prime
Prime number"
Do you need help or just mocking us?
Can you explain the algorithm you're using for this?(only if you're willing to, there's no pressure)

[pseudorandom21]

void main()

Whatever happened to "int main()" in the 80s anyway?

[cse.avinash]

check this line instead:--

for(i=3; i<=a/2; i=i+2)

it will decrease the time complexity, I have checked this for few numbers and this is working.

[Adak]

For finding larger primes, quicker:

1) #include <math.h>
2) in the outer loop, save the sqrt() of the number being checked, add one to it
3) in the inner for loop, stop at < that number you just saved. You never need
to go any higher.

4) if you have the memory, you can "mark off" the numbers you don't need to check in the future, with every number you try, so:

try is 2: just increment as you are doing, no change needed
try is 3: mark off 6, 9, 12, 15, 18, 21, etc.
try is 5: mark off 10, 15, 20, 25, 30, etc.
try is 7: mark off 14, 21, 28, 35, 42, etc.

using an array of ints. There is some repetition, but "marking off" could be just zero'ing out an array, which is very much faster than using %.

For more info on this, look up the Sieve of Eratosthenes, on Wikipedia.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Nice animation of it, makes it clear.

[ashok1514]

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

int main()
{
    int a,i;
    printf("\n Enter a number : ");
    scanf("%d",&a);
    for(i=2; i<=a/2; i++) {
        if(a%i==0) {
            printf("\n Not a prime number");
            getch();
            exit(0);
        }
    }
    int a,i;
    printf("\n Enter a number : ");
    scanf("%d",&a);
    for(i=2; i<=a/2; i++) {
        if(a%i==0) {
            printf("\n Not a prime number");
            exit(0);
        }
    }
    if(a==1)
        printf("\n Not a prime number");
    else
        printf("\n Is prime number");
    getch();
}

Just run this code u will the perfect solution for ur problem

[vinodhsml]

with pleasure

[NP-complete]

@ashok1514: look what a disaster you did! Now the op (vinodhsml) will simply copy the code without trying out Adak's advise.

And oh, guess what, if the op blindly copies it, he'll run into problems as your snippet contains repeated code(!!!).

And also, the code you gave him is not optimal. Only Adak's solution (with the sqrt) is the presently optimal solution.

daniweb has a principle; it promotes learning and not copy-pasting. So, there...

[Prateek nandan]

\\i post a new method according definition prime :devide by 1 and itself//
#include<stdio.h>
#include<conio.h>
int main(){
int num,i,j,count=o;
printf("enter a number");
scanf("%d",&num);
for(i=1;i<=num;i++){
if(num%i==0)
count++;
}
if(count==2)/*devide by 1 and itself so count=2*/
printf("number is prime");
else
printf("number is not prime");
}
//any problem concern me........

[reojavier]

simply get the number of factor/s to determine whether prime or not:

for(a=2; a<x; a++)
{
 if(x % a == 0)
 {
   factor++;
 }
}

then check the definition of prime numbers, if happens the factors of x is 5,000,001 then it is not prime. :O