C Showing prime numbers using For statement

Question

I'm newly new to C programming , started about a week ago ! And i'm getting into loops i faced a problem writing a C program to show prime numbers less-than 100 . I'll share up the C code i've written and its output ! I'll wait for your help and your remarks about it

    #include<stdio.h>

    main(){

    int i,d,k;

    for( i=1 ; i<=100 ; i++ ){
        d=0;
        for( k=1 ; k<=i ; k++ ){
            if( i%k==0){
                d=d+1;
            }
        }
        if( d==1 ){
            printf("\n%d",i);
        }
    }

    getchar();
    getchar();

    }

Output:

Thanx !

basically you had a bad condition for prime numbers. you are counting number of factors of i. you will at least have 1 and i itself as a factor. And since you requires only 1 factor to be found, you will only find 1 that fulfill that requirement. Instead of doing that, you can require that there is no factor of i between 2 and i/2. — Xiaolei Zhu, Nov 28 '13 at 19:49
You don't even have to go farther than sqrt(i). (Hint: you don't actually need `sqrt` in the loop condition if you do this) — Kninnug, Nov 28 '13 at 20:02
This is actually one of those classical programming homework assignments. I suggest you analyze the correct algorithm shown here: http://www.programmingsimplified.com/c/source-code/c-program-for-prime-number — turnt, Nov 28 '13 at 20:09

score 2 · Accepted Answer · answered Nov 28 '13 at 20:54

Here you go...e.g 5 has to factors (1 and 5):

#include<stdio.h>

    main(){

    int i,d,k;

    for( i=1 ; i<=100 ; i++ ){
        d=0;
        for( k=1 ; k<=i ; k++ ){
            if( i%k==0){
                d=d+1;
            }
        }
        if( d==2 ){
            printf("\n%d",i);
        }
    }

    getchar();
    getchar();

    }

score 1 · Answer 2 · edited Dec 07 '13 at 17:42

1

#include<stdio.h>

main(){

    int i,d,k;

    for( i=1 ; i<=100 ; i++ ){
        d=0;
        for( k=1 ; k<=i ; k++ ){
            if( i%k==0){
                d=d+1;
            }
        }
        if( d==1 ){
            printf("\n%d",i);
       }
   }

   getchar();
}

edited Dec 07 '13 at 17:42

Dan Is Fiddling By Firelight

5,981
17
77
128

answered Dec 07 '13 at 17:15

Tayyab Kazmi

376
4
19

What is your reasoning for this code? For the beginner to C programming, showing only code does not help. Edit your answer to include your reasoning that makes sense in the context of the OP's question. – Dec 07 '13 at 17:38

score 0 · Answer 3 · answered Nov 28 '13 at 20:34

Reading your algorithm with i=2.

 d=0
 k=1 : 2%1=0 so d=1
 k=2 : 2%1=0 so d=2

So 2 is not prime...Alrggg

There are many way to correct and make your code run faster. Computing sqrt(i) for all i might be "costly" if i<100, but doing something similar from time to time would be a good trick...

More : no need to continue once a divisor is found More : Eratosthenes is your friend... More : smaller divisor is always prime...Store ? More : look Wikipedia in fact... http://en.wikipedia.org/wiki/Primality_test Bye,

Francis

score 0 · Answer 4 · edited May 23 '17 at 12:08

The main function should return an int: What should main() return in C and C++?.

Also, consider making a function to test if a number is prime. This is a cleaner approach, but I guess you did not learned them yet.

The algorithm you are using is not efficient at all. There are many ways to improve it.

To correct it, you should know that a prime number has 2 divisors (except 1, but it is not a prime): 1 and itself. Your second for loop checks for those 2, so a number is prime if d is 2, not 1.

Even if you are a beginner, you should try to improve this algorithm. Firstly, it is enough to check until sqrt(i) for divisors. Also, when you find a divisor, you can stop the loop. Also, as 1 is always a divisor, you may start the second loop with 2.

That's it ! the mistake was (d==1) i should've made (d==2) as a condition :D — , Nov 28 '13 at 21:27

Vallabh Patade · Answer 5 · 2013-11-28T20:46:20.767

You are using d as a flag to detect if number was ever divisible during the inner for loop. Use it right. Whenever no is divisible, set flag to 1 indicating it's not prime. If flag is unaffected through the inner loop, means number is prime. You should also consider returning an int value from main function indicating exit status.

Change the code as follows.

  #include<stdio.h>
  main(){
     int i,d,k;
    for( i=2 ; i<=100 ; i++ ){
         d=0;
          for( k=2 ; k<i ; k++ ){
             if( i%k==0){
                d=1; //Set the flag to 1 indicating no. is not prime and break
                break;
             }
          }
         if( d==0){ //Means flag the was unaffected throughout the loop i.i. Prime
             printf("\n%d",i);
         }
     }
    getchar();
    return 0;
 }

thnx ! the answer of Asim Awan was the closest :D – Nov 28 '13 at 21:31 — , Nov 28 '13 at 21:31
Closest.?? Closest to what.? – Vallabh Patade Nov 28 '13 at 22:53 — Vallabh Patade, Nov 28 '13 at 22:53

C Showing prime numbers using For statement

5 Answers5