C prime number program help

[SgtBot]

I am writing a program in C that checks for prime numbers within a range of numbers. The program seems to be working fine, but there are a couple problems that I haven't been able to figure out. Here is the code:

#include<stdio.h>

main()
{
    int counter = 0;
    int lower_bound, upper_bound, num_counter, i;

    printf("Lower bound?\n");
    scanf("%d", &lower_bound);
    printf("Upper bound?\n");
    scanf("%d", &upper_bound);

    num_counter = lower_bound;

    while (num_counter <= upper_bound)
    {
        if (num_counter <= 1)
        {
            printf("%d", num_counter);
            printf(" is not prime\n");
            break;
        }
        else if (num_counter > 1)
        {
            for (i = 2; i <= num_counter / 2; i++)
            {
                if ((num_counter % i) == 0)
                {
                    printf("%d", num_counter);
                    printf(" is not prime\n");
                    break;
                }
                if ((num_counter % i) != 0)
                {
                    counter = counter + 1;
                    printf("%d", num_counter);
                    printf(" is prime\n");
                    break;
                }
            }
        }
        num_counter = num_counter + 1;
    }
    printf("%d\n", counter);
    int num_range = upper_bound - lower_bound + 1;
    printf("%d\n", num_range);
    float prime_density = counter / num_range;
    printf("%f\n", prime_density);
    

    /*printf("Over the interval from ");
    printf("%d", lower_bound);
    printf(" to ");
    printf("%d", upper_bound);
    printf(" inclusive, the prime density was ");
    printf("%f", prime_density);*/
}

The first problem I have is that the program does not like the number 3 as a lower_bound value, here is the output when I try a range from 3 to 6:

Lower bound?
3
Upper bound?
6
4 is not prime
5 is prime
6 is not prime
1
4
0.000000

It will function almost perfectly but will not print out anything for 3 or add one to the counter.

The next problem I have is with a float called prime_density. I have the string stuff commented out so I could try and figure out why it kept printing out 0.000000. As you can see above, the result for prime_density should be 0.25 if the counter is at 1 and the num_range is at 4, but it just prints 0.000000 every time, even with number ranges that don't include 3:

Lower bound?
7
Upper bound?
10
7 is prime
8 is not prime
9 is prime
10 is not prime
2
4
0.000000

Any help or advice to fix this would be greatly appreciated!

[colonel_mortis]

I'll annotate your source with my comments

#include<stdio.h>

main()
{
    int counter = 0;
    int lower_bound, upper_bound, num_counter, i;

    printf("Lower bound?\n");
    scanf("%d", &lower_bound);
    printf("Upper bound?\n");
    scanf("%d", &upper_bound);

    num_counter = lower_bound;

    while (num_counter <= upper_bound)
    {
        if (num_counter <= 1)
        {
            printf("%d", num_counter);
            printf(" is not prime\n");
            break; // Don't want to break here, otherwise if lb=0 and ub=5, it will say "0 is not prime" then stop.
        }
        else if (num_counter > 1)
        {
            for (i = 2; i <= num_counter / 2; i++)
            {
                if ((num_counter % i) == 0)
                {
                    printf("%d", num_counter);
                    printf(" is not prime\n"); // nitpick: You can simplify the line above and this
                                               // to printf("%d is not prime\n", num_counter);
                    break; // This break is correct, but you probably want to add a prime = false
                           // first, as explained below
                }
                if ((num_counter % i) != 0)
                {
                    counter = counter + 1; // What is counter for? It looks like it's just a debug
                                           // variable, right?
                    printf("%d", num_counter);
                    printf(" is prime\n"); // This is your bug. All you know here is that it's not
                                           // divisible by i (=2), but you've not tested other values
                                           // yet. You only know it's prime if you get to the end of
                                           // your loop and still haven't found any evidence that it's not.
                    // You probably want to add prime = true before the loop, then set it to false if
                    // you find evidence that it's not. Then...
                    break;
                }
            }
            // ... add a test here (after the end of the num_counter loop) to see whether it was prime or not
        }
        num_counter = num_counter + 1;
    }
    printf("%d\n", counter);
    int num_range = upper_bound - lower_bound + 1;
    printf("%d\n", num_range);
    float prime_density = counter / num_range;
    printf("%f\n", prime_density);
}

 

[SgtBot]

Thanks for the help! However, I'm using ANSI C (I think version 90.x) instead of C++, and there are no boolean expressions like True or False in this version.. I could set up a flag with a 1 or 0 variable instead maybe? Also, I rewrote the code a bit and was able to fix everything but I don't think it is as efficient as your method. Here it is:

#include<stdio.h>

main()
{
    int counter = 0;
    int lower_bound, upper_bound, num_counter, i;

    printf("Lower bound? ");
    scanf("%d", &lower_bound);
    printf("Upper bound? ");
    scanf("%d", &upper_bound);

    num_counter = lower_bound;

    while (num_counter <= upper_bound)
    {
        if (num_counter <= 1)
        {
            printf("    %d is not prime\n", num_counter);
        }

        else if (num_counter == 2)
        {
            counter++;
            printf("    %d is prime\n", num_counter);
        }

        else if (num_counter == 3)
        {
            counter++;
            printf("    %d is prime\n", num_counter);
        }

        else if (num_counter > 1)
        {
            for (i = 2; i <= num_counter / 2; i++)
            {
                if ((num_counter % i) == 0)
                {
                    printf("    %d is not prime\n", num_counter);
                    break;
                }
                if ((num_counter % i) != 0)
                {
                    counter++;
                    printf("    %d is prime\n", num_counter);
                    break;
                }
            }
        }
        num_counter = num_counter + 1;
    }
    int num_range = upper_bound - lower_bound + 1;
    float prime_density = (float)counter / (float)num_range;

    printf("Over the interval from ");
    printf("%d", lower_bound);
    printf(" to ");
    printf("%d,", upper_bound);
    printf(" inclusive, the prime density was ");
    printf("%f\n", prime_density);
}

I removed the break in the first if statement and changed the printf lines to printf("    %d is/ is not prime\n", variable). Also, the counter is to count the number of prime numbers it finds, and then divides that by the range of numbers checked to get the density of prime numbers in a given range. I also wrote in 2 more else if statements to automatically say prime if the number is a 2 or a 3. I will try to implement your method with a flag with a 1 or 0 value and see if I can make it more efficient. Thanks!

[elpiop]

edit: Seems you fixed it in your post at the same time I commented
 

Spoiler

 

You set num_counter = lower_bound

When you input 3, num_counter = 3

So, for this loop: 
 for (i = 2; i <= num_counter / 2; i++)

In this case, num_counter / 2 =  3/2 = 1.5, (truncated becomes 1, as it is an int)

i <= 1, the body of the loop won't be executed

The of that loop will not execute for any integer <= 3

 

 

 

 

 

[colonel_mortis]

2 minutes ago, SgtBot said:

Thanks for the help! However, I'm using ANSI C (I think version 90.x) instead of C++, and there are no boolean expressions like True or False in this version.. I could set up a flag with a 1 or 0 variable instead maybe? Also, I rewrote the code a bit and was able to fix everything but I don't think it is as efficient as your method. Here it is:

#include<stdio.h>

main()
{
    int counter = 0;
    int lower_bound, upper_bound, num_counter, i;

    printf("Lower bound? ");
    scanf("%d", &lower_bound);
    printf("Upper bound? ");
    scanf("%d", &upper_bound);

    num_counter = lower_bound;

    while (num_counter <= upper_bound)
    {
        if (num_counter <= 1)
        {
            printf("    %d is not prime\n", num_counter);
        }

        else if (num_counter == 2)
        {
            counter++;
            printf("    %d is prime\n", num_counter);
        }

        else if (num_counter == 3)
        {
            counter++;
            printf("    %d is prime\n", num_counter);
        }

        else if (num_counter > 1)
        {
            for (i = 2; i <= num_counter / 2; i++)
            {
                if ((num_counter % i) == 0)
                {
                    printf("    %d is not prime\n", num_counter);
                    break;
                }
                if ((num_counter % i) != 0)
                {
                    counter++;
                    printf("    %d is prime\n", num_counter);
                    break;
                }
            }
        }
        num_counter = num_counter + 1;
    }
    int num_range = upper_bound - lower_bound + 1;
    float prime_density = (float)counter / (float)num_range;

    printf("Over the interval from ");
    printf("%d", lower_bound);
    printf(" to ");
    printf("%d,", upper_bound);
    printf(" inclusive, the prime density was ");
    printf("%f\n", prime_density);
}

I removed the break in the first if statement and changed the printf lines to printf("    %d is/ is not prime\n", variable). Also, the counter is to count the number of prime numbers it finds, and then divides that by the range of numbers checked to get the density of prime numbers in a given range. I also wrote in 2 more else if statements to automatically say prime if the number is a 2 or a 3. I will try to implement your method with a flag with a 1 or 0 value and see if I can make it more efficient. Thanks!

Your fixed code just adds a workaround for 3, but it doesn't solve the underlying issue. For example, it still thinks that 25 is prime, because it's not divisible by 2.

0 and 1 are indeed the C analogues of false and true, and using them as false/true to track whether the number has any divisors should work.

[HunterAP]

The only "true" way to check if a number is prime is to check if it's divisible by all primes that are less than the square root of your number.
For example, 29 would need to get tested by all numbers less than sqrt(29) ~= 5.3851648071345040312507104915403 -> 5.
Normally I'd say to make an array to store all of your prime numbers so you can calculate them properly, but if say you make the lower bound 29, then you'll be missing plenty of prime numbers that would normally be used to calculate any future prime numbers (IE 3).

 

You best bet is to calculate every prime number from 1 to your upper bound and only store the primes that are greater than your lower bound.

Basically:

1. Make an array with upper_bound number of elements (so if upper_bound = 5 then the size of the array is 5). For this example I'll call it "myArray".

2. Have a variable track how many elements in the array are actually filled. Iterating through arrays is dangerous unless you know both the max size and the number of elements with values inside the array. For this example I'll call it "filled_size".

3. Make a loop that goes from 1 to your upper bound:

for (int i = 2; i < upper_count; i = i + 1)

4. Get the square root of i

5. Make another loop inside the for loop to check if i is divisible by every previous prime that you would store in your array. If the array is empty (like when you first check if the number 2 is prime) then simple insert 2 into the array.

for (int i = 2; i < upper_count; i = i + 1)
{
  int temp = (int)floor(sqrt(i));
  bool isPrime = 0;

  for (int j = 0; j < filled_size; j = j + 1)
  {
    //If temp mod any value in your array of primes, then the number is not prime.
    //For example, if i = 24 then sqrt(24) ~= 4.8989794855663561963945681494118 -> rounded down to 4.
    //The array should already have every prime up to 24, so 2, 3, 5, etc.
    //If we take 4 % 2, we get 0 since 4 / 2 has no remainder.
    if (temp % myArray[j] == 0)
    {
      //Number is not prime.
      isPrime = 0;
      break;
    }
    else //If we get any other remainder, then we must continue the loop to check for the number's prime-ness.
    {
      continue;
    }
    isPrime = 1;
  }
  //If we checked using every prime number in our array, then the number we're testing is a prime.
  //That means we want to insert it into out array.
  if (isPrime)
  {
    myArray[filled_size] = i;
    filled_size = filled_size + 1;
  }
}

6. We also need to make sure we only print prime numbers within our range (lower_bound -> upper_bound), so we can add checks for that wi

for (int i = 2; i < upper_count; i = i + 1)
{
  int temp = (int)floor(sqrt(i));
  bool isPrime = 0;

  for (int j = 0; j < filled_size; j = j + 1)
  {
    //If temp mod any value in your array of primes, then the number is not prime.
    //For example, if i = 24 then sqrt(24) ~= 4.8989794855663561963945681494118 -> rounded down to 4.
    //The array should already have every prime up to 24, so 2, 3, 5, etc.
    //If we take 4 % 2, we get 0 since 4 / 2 has no remainder.
    if (temp % myArray[j] == 0)
    {
      //Number is not prime.
      isPrime = 0;
      printf("    %d is not prime\n", i);
      break;
    }
    else //If we get any other remainder, then we must continue the loop to check for the number's prime-ness.
    {
      continue;
    }
    printf("    %d is prime\n", i);
    isPrime = 1;
  }
  //If we checked using every prime number in our array, then the number we're testing is a prime.
  //That means we want to insert it into out array.
  if (isPrime)
  {
    myArray[filled_size] = i;
    filled_size = filled_size + 1;
  }
}