CODEWITHSUNDEEP
c
ninjamonkeym
ninjamonkeym

Reputation: 21

Program to find prime numbers prints out two

I am fairly new to programming and I wanted to try to write a program to find the amount of prime numbers with in a range of numbers. When I run this program through the compiler, I dont get any errors, but when I try to actually run the program it says that there are only 2, which is incorrect. I think it should be about 168. If you could help point out my error I would appreciate it. Thanks in advance! 

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

void primeFinder(void);

int main(void)
{
    printf("Prime numbers from 1 to 1000:\n\n");
    primeFinder();

    return 0;
}


void primeFinder(void)
{
    int i;
    int j;
    int k;
    int n_primes = 0;

    //i is the number to be tested:
    for ( i = 2 ; i <= 1000 ; i++ )
    {
        //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
        for ( j = 2, k = 0 ; j <= sqrt(i) ; j++ )
        {
            //i is not prime, whatever is the value of j:
            if ( i % j == 0 )
            {
                //If remainder is 0, there is no need to test that i anymore:
                break;
            }
            else
            {
                k++;
            }

        } //End of inner for
            //i is prime:
        if ( k == i - 2 )
        {
            printf("%d\t", i);
            n_primes++;
        }
    } //End of outer for
    printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);
}

Upvotes: 1

Views: 2934

Answers (8)

cse
cse

Reputation: 4104

The problem is in line

if ( k == i - 2 )

Value of i is fixed and k is varing. So following lines are executing only for i=2 and 3. So you are getting answer 2.

if ( k == i - 2 )
{
      printf("%d\t", i);
      n_primes++;
}

You may found following code useful:

#include<stdio.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
int isPrimeNumber(int num)
{
    int i=2;
    int len=sqrt(num);
    if(num<2) return FALSE;
    while(i<=len)
    {
        if(num%i==0)
        {
            return FALSE;
        }
        i++;
    }

    return TRUE;
}

int countPrimeNumbersInRange(int start, int end)
{
    int count=0;
    while(start<=end)
    {
        if(isPrimeNumber(start))
        {
            printf("%d\t",start);
            count++;
        }
        start++;
    }
    return count;
}

int main()
{
    printf("\n\nIt was found %d prime(s) in the inverval considered.\n", countPrimeNumbersInRange(1, 1000));
    return 0;
}

Upvotes: 0

wjmolina
wjmolina

Reputation: 2675

One advice I give beginner programmers that I found to be actually helpful is: "think modularity!" In other words, train yourself to divide and conquer; how can I break the problem down into its fundamental components?

A good skeleton for your program would be the following:

#include <stdio.h>

typedef int BOOL;

#define TRUE 1
#define FALSE 0    

BOOL is_prime(int number);

int main()
{
    printf("Prime numbers between 1 and 1000:\n");

    int i;
    for (i = 1; i <= 1000; ++i)
    {
        if (is_prime(i))
        {
            printf("%d\n", i);
        }
    }

    return 0;
}

// ...

This is because, later on, if you need to determine whether a number is prime or not, you can simply copy and paste your existing implementation.

Here is one implementation of is_prime I often use and does the job fairly well:

BOOL is_prime(int number)
{
    // If the number is less than two, then it is not prime.
    if (number < 2)
    {
        return FALSE;
    }

    // If the number is two, then it is prime.
    if (number == 2)
    {
        return TRUE;
    }

    // If the number is even, then it is not prime.
    if (number % 2 == 0)
    {
        return FALSE;
    }

    // Try and divide the number by all odd numbers
    // less than or equal to its square root. If
    // we can, then it is not prime. Otherwise, it is.
    int i;
    for (i = 3; i * i <= number; i += 2)
    {
        if (number % i == 0)
        {
            return FALSE;
        }
    }
    return TRUE;
}

Upvotes: 1

Freddie
Freddie

Reputation: 891

If a number is prime, k will increment to the value of sqrt(i). The if condition will not always be true, as you have seen.

Instead of using a counter, you just need a flag to know if it's prime. Maybe something like this:

    //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
    for ( j = 2, k = 1 ; j <= sqrt(i) ; j++ )
    {
        //i is not prime, whatever is the value of j:
        if ( i % j == 0 )
        {
            //If remainder is 0, there is no need to test that i anymore:
            k = 0;
            break;
        }
    } //End of inner for
    if (k) // i is prime
    {
    ...

Upvotes: 0

netanelw
netanelw

Reputation: 121

It seems like you changed the algorithm in the middle, i.e. instead of checking for divisiors up to i-1 (which is wasteful), you tested until sqrt(i).

The problem is you only changed the loop condition, but didn't update the following condition:

if ( k == i - 2 )

You have 2 options:

  1. roll back to the naive algorithm and change the loop condition to:

    for( j = 2, k = 0 ; j <= i-1 ; j++ )

  2. change your program logic so you only need to know if a divisor other than 1 exists, regardless of the number of such divisors.

Upvotes: 0

nrcrast
nrcrast

Reputation: 171

It's your check. The way you're doing this is a little strange. I think an easier way to do this is to create a flag and set it to true. So you assume the number is prime. As you're going through, if you find that the number isn't prime, set the flag to false. After, check if the flag is still true and print the result if it is. Here's what I'm talking about:

  int i;
int j;
int k;
int n_primes = 0;
bool flag;

//i is the number to be tested:
for ( i = 2 ; i <= 1000 ; i++ )
{
    //Assume it's prime
    flag=true;
    //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
    for ( j = 2 ; j <= sqrt((double)i) ; j++ )
    {
        //i is not prime, whatever is the value of j:
        if ( i % j == 0 )
        {
            //If remainder is 0, there is no need to test that i anymore:
            flag=false;
            break;
        }
    } //End of inner for
        //i is prime:
    if ( flag==true )
    {
        printf("%d\t", i);
        n_primes++;
    }
} //End of outer for
printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);

Upvotes: 0

Brendan Long
Brendan Long

Reputation: 54242

Why bother keeping track of k? Just set a flag to tell you if the number is prime:

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

int num_primes(int limit) {
    int i;
    int j;
    int n_primes = 0;
    bool is_prime; /* note stdbool.h in the includes */

    for (i = 2; i <= limit; i++) {
        is_prime = true;
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        /* This could be written as `if (is_prime) n_primes++;` */
        n_primes += is_prime;
    }
    return n_primes;
}

Upvotes: 0

Gavin Smith
Gavin Smith

Reputation: 3154

The inner loop is exited after j reaches the square root of i. Therefore k does not count the full number of numbers that do not divide i.

Upvotes: 0

Zac Wrangler
Zac Wrangler

Reputation: 1445

if ( k == i - 2 ) this check is wrong, the previous block only loops against sqrt(i) - 2 numbers. You need to check against sqrt(i) -2

Upvotes: 0

Related Questions