CODEWITHSUNDEEP
c
Benjamin Kušen
Benjamin Kušen

Reputation: 1

Finding prime number in c, my if doesnt do its job

I have to make a code that will find prime numbers in given interval, and the if (y % j == 0) wont work, why is that?

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

int main(void) {
    int a, b, br=0, i, j, brojac=0, y;
    scanf("%d %d", &a, &b); 
    int p[b-a];
    for(i=a; i<=b; i++){
        p[br]=i;
        br++;
    }

    for(i=0; i<br; i++){
        y=p[i];
        for(j=1; j<= (int) sqrt(p[i]); j++){
           if(y%j == 0){
               printf("\n%d", p[i]);
               brojac++;
               break;
           }
        }
    }

    printf("\n%d", brojac);
    return 0;
}

Upvotes: 0

Views: 83

Answers (3)

chux
chux

Reputation: 153447

Code problems:

  1. Minor: scanf("%d %d", &a, &b); No check for failure.

  2. br=0,... int p[b-a]; for(i=a; i<=b; i++){ p[br]=i; br++; will eventfully attempt access 1 passed p[].

  3. for(j=1; ... if(y%j == 0){ --> y%1 == 0 is always true.

  4. j<= (int) sqrt(p[i]); is a poor test as sqrt() is expensive and a weak sqrt() may return a value just under the expected whole number one.

  5. if(y%j == 0){ printf("\n%d", p[i]); prints numbers that are not prime.

  6. Logic error in for(j=1; loop as that loop eliminates candidate primes and should not print anything.

Too many problems.

Instead, use the fast Sieve of Eratosthenes

#include <stdbool.h>
#include <stdio.h>

void Sieve_of_Eratosthenes(int a, int b) {
  printf("Primes from %d to %d\n", a, b);
  bool prime[b+1];
  for (int i = 2; i<=b; i++) {
    prime[i] = true;
  }
  for (int i = 2; i<=b; i++) {
    if (prime[i]) {
      for (int j = i+i; j <= b; j += i) {
        prime[j] = false;
      }
    }
  }
  for (int i = a;i<=b; i++) {
    if (prime[i]) printf("%d\n", i);
  }
}

int main(void) {
  Sieve_of_Eratosthenes(7,50);
}

Output

Primes from 7 to 50
7
11
13
17
19
23
29
31
37
41
43
47

Upvotes: 0

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28830

Doing for(j=1 ... will have all numbers match y % 1, so start from 2.

Then your algorithm as it is will displays numbers that are not prime, once the problem above is corrected.

Instead, set a variable prime to 1, and reset it to 0 when the number is seen as not a prime. After the loop display the number if it is still flagged 'prime':

for(i=0; i<br; i++){
  y=p[i];
  int prime=1;  // <===== start telling it's a prime
  for(j=2; j<= (int) sqrt(p[i]); j++){ // <=== start from 2
     if(y%j == 0){
        prime = 0; // <==== Not a prime
        break;
     }
  }
  if (prime) {  // <=== after the loop, still a prime
     brojac++;
     printf("\n%d", y);
  }
}

Finally you might want to follow advice from the comments below your question.

Upvotes: 1

Pablo DbSys
Pablo DbSys

Reputation: 542

The FOR condition j<= (int) sqrt(p[i]). I would do a function

bool isPrime(int n){
  int i;
  if(n == 2)
    return true;
  if(n%2 == 0 || n==1 )
    return false;
  for(i=2; i<=n/2; i++){
    if(n%i == 0)
        return false;
  }
  return true;
}

Upvotes: 1

Related Questions