Getting all prime numbers between 2 and 100 in C

Question

This is my code which is supposed to output prime numbers only.

#include <stdio.h>
int prime(int n){
    int j;
    for (j=2;j<=n/2;j++){
        if((n%j)==0){
            return 0;
        }
        else{
            return 1;
        }
    }
}
void main(){
    int i,p;
    for (i=2;i<=100;i++){
        p=prime(i);
        if(p==1){
            printf("%d \n",i);
        }
    }
}

The result is 2,3,7,9,11,13,15....

not 2,3,5,7,11,13....

What did I do wrong?

What purpose does the `for` loop in `prime` serve if it always returns before it has a chance to repeat? — David Schwartz, Oct 15 '12 at 09:07
another way to do this, without any remainders, is an "unrolled" sieve of Eratosthenes: http://stackoverflow.com/questions/5200879/printing-prime-numbers-from-1-through-100/12543821#12543821 — Will Ness, Oct 15 '12 at 20:47

score 5 · Accepted Answer · answered Oct 15 '12 at 09:08

5

Your probably want:

int prime(int n){
    int j;
    for (j=2;j<=n/2;j++)
        if((n%j)==0)
            return 0;
   return 1;
}

answered Oct 15 '12 at 09:08

David Schwartz

179,497
17
214
278

Your code doesn't actually loop because it always returns on the first check. If `(n%j)` is not equal to zero, you don't want to return, you need to test for other possible factors. – David Schwartz Oct 15 '12 at 09:19

score 2 · Answer 2 · answered Oct 15 '12 at 09:14

2

Prime Numbers are numbers which are only divisible by two numbers. eg 2,3,5,7,11 etc.

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

answered Oct 15 '12 at 09:14

alloc_iNit

5,173
2
26
54

1

Pretty strange that you make extra work having the loop check if a number is divisible by both one and itself just to make extra work having to count the number of factors. Also, there's no C function called `getch`. Is your program gratuitously platform-specific? And why wait for a key to be hit anyway? That just makes it difficult for someone to redirect the output of your program to a file. – David Schwartz Oct 15 '12 at 09:19

score 1 · Answer 3 · answered Oct 15 '12 at 09:16

1

Try this :

int prime(int n){
    int j;
    int isPrime = 1;
    for (j=2;j<=n/2;j++){
        if((n%j)==0){
            isPrime = 0;
            break;
        }
    }
    return isPrime;
}

answered Oct 15 '12 at 09:16

rkosegi

14,165
5
50
83

जलजनक · Answer 4 · 2012-10-15T10:34:10.887

If you're trying to find out Prime numbers up to a given number(in your case 2..100) building a prime table will speed up the process:

NOTE: it's important that inputs are sequential to help build prime table.

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

/* Building a prime table for fast look up
 * NOTE : Numbers should be input from 2 to n in a sequential pattern to help build prime table;  */

# define PRIME_TAB_MAX 200

int prime_specific(int num)
{
    static int primeTab[PRIME_TAB_MAX] = { 0, };
    static int primeCount = 0;
    int check_limit ;
    unsigned int idx;

    if (num < 2)
        return 0;

    if (primeCount > 0) {
        check_limit = (int)sqrt(num);
        for (idx = 0; idx < primeCount && primeTab[idx] <= check_limit; idx++) {
            if (0 == (num % primeTab[idx])) {
                return 0;
            }
        }
    }
    else {
        for (idx = 2; idx <= num / 2; idx++)
            if (0 == (num % idx))
                return 0;
    }

    if (primeCount < PRIME_TAB_MAX) {
        primeTab[primeCount++] = num;
        return 1;
    }
    else {
        fprintf(stderr, "\nERROR: Prime Table is full");
        return (-1); //Internal error
    }
}

int main(void)
{
    unsigned int idx;
    int status ;

    for (idx = 2; idx <= 1000; idx++) {

        status = prime_specific(idx);

        switch (status)
        {
        case 1:
            fprintf(stderr, "%d\n", idx);
            break;
        case 0:
            //Do nothing
            break;
        default:
            fprintf(stderr, "\nERROR:Internal Error");
            return (-1);
        }
    }
    return 0;
}

score -1 · Answer 5 · edited Mar 06 '13 at 17:07

-1

Code:

#include <stdio.h>

int main ()

{

   /* local variable definition */

   int i, j;

     for(i=2; i<100; i++)
    {
      for(j=2; j <= (i/j); j++)

        if(!(i%j)) break; // if factor found, not prime

      if(j > (i/j)) printf("%d is prime\n", i);
    }

   return 0;

}

edited Mar 06 '13 at 17:07

fedorqui

275,237
103
548
598

answered Mar 06 '13 at 16:44

metropolis10

11
1

Getting all prime numbers between 2 and 100 in C

5 Answers5

Linked