About Prime Generation in "C" - What is wrong with my code ? -

I'm a third year irregular CS student and ,i just realized that i have to start coding.

I passed my coding classes with lower bound grades so that i haven't a good background in coding&programming.

I'm trying to write a code that generates prime numbers between given upper and lower bounds. Not knowing C well, enforce me to write a rough code then go over it to solve. I can easily set up the logic for intended function but i probably create a wrong algorithm through several different ways.

Here I share my last code, i intend to calculate that when a number gives remainder Zero , it should be it self and 1 , so that count==2; What is wrong with my implementation and with my solution generating style? I hope you will warm me up to programming world, i couldn't find enough motivation and courage to get deep into programming.

Stdio and Math.h is İncluded

int primegen(int down,int up)
{   
    int divisor,candidate,count=0,k;

    for(candidate=down;candidate<=up;candidate++)
    {
        for(divisor=1;divisor<=candidate;divisor++)
        {
            k=(candidate%divisor);
     开发者_StackOverflow社区   }
        if (k==0) count++;
        if(count==2)
        {
            printf("%d\n", candidate);
            count=0;
        }
        else
        {
            continue;
        }
    }
}

int main()
{
    primegen(3,15);
    return 0;
}

---

You're including 1 and the candidate in your candidate%divisor tests, both of which will always return 0, so every number you test will appear prime.

Instead of this:

for(divisor=1;divisor<=candidate;divisor++)

do this:

for(divisor=2;divisor<candidate;divisor++)

update

There are too many things wrong with your code to list, but here are a couple anyways:

• you're checking the result of candidate%divisor outside the for loop
• by the time you check k, k is always candidate%candidate, or 0
• you only ever check k once, after the divisor loop
• don't continue at the end of your loop, that's what happens by default

Look, here is some pseudo-code for the simplest possible implementation. Try to find where your code deviates from this:

for candidate = down to up
  // assume the candidate is primt
  prime = true

  // check all divisors from 2 to the candidate - 1, inclusive
  for divisor = 2 to candidate - 1
    if candidate % divisor == 0
      // divisor is a factor of candidate
      // candidate isn't prime, so we can stop checking
      prime = false
      break
    end if
  next divisor

  // if prime is still true, we successfully tested every number from 2..candidate
  // and found no factors
  if prime
    print "candidate {candidate} is prime!"
  end if
next candidate

---

• In your inner loop you calculate candidate%divisor for all divisors, but only after the loop is finished you check if count should be incremented. So you only increment it only once per candidate, for the last divisor checked.
• Also you do not reset count for each candidate in the outer loop. So you count the found divisors for all candidates together while you want to count for each candidate individually.

---

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

int primegen(unsigned int down,unsigned int up)
{   
int *ar;
int divisor,candidate,count=0,k;

for(candidate=up;candidate>=down;candidate--)
    {   count=0; 
        for(divisor=2;divisor<candidate;divisor++)
            {if (((candidate%divisor)==0)) count++; }
            if(count==0) {printf("%d\n",candidate); count=0;}

    }
}
int main()
{
primegen(3,15);
return 0;
}

Finally i have corrected my solution. The main problem was that i weren't assigning count to zero before the second for loop. I changed the order of candidate (big to small) and i corrected little syntax mistakes.

Thanks all you for your encouraging help and answers. :) I'm happy to have this done , so i can pass through other algorithms&problems.

---

Some hints to keep in mind

if(!(candidate & 0x01))
    // We know its even so we can stop

if(candidate == potential_factor)
    // We can stop

if(candidate % potential_factor == 0)
    // The potential factor IS a factor and we can stop

---

Someone has reformatted the code for clarity from its original submitted form. In doing so, they've modified one of the three mistakes in the code.

The first mistake was that the second for statement did not have brackets after it. As a result, the loop body consisted only of the statement which followed the second for statement. From reading the code, it's clear that the questioner intended everything after the second loop statement to be executed repeatedly. This is not what was happening.

Essentially, the idea was: for each number in the range, try all numbers between 1 and the candidate. Count the number of those which divide it. See if there are exactly 2. This is a correct algorithm and the answer which say to not divide by 2 is wrong.

However, the implementation was doing this: for each number in range, divide the candidate by every number between 1 and the candidate. Then, once you've done all that division, check to see if the last one came out even and if so, add 1 to the count. So, what's happening is that you're only actually checking to see if candidate % candidate == 0 which it always does.

The second mistake, is that the count is only reset when it gets to 2. So, what's happening is that the code, for any input, will return every other number. For each candidate, count++ happens exactly once. So it reaches 2 and gets reset every other time.

The third mistake is that once the inner-most loop is fixed, then the continue will do the wrong thing since it only continues the inner-most loop.

---

I know your code is for educational purposes only, however you should consider Sieve of Eratosthenes as it would probably be the fastest algorithm for your problem. What it basically does is:

1. At first consider all numbers prime numbers.
2. Starting off with 2, you consider all the multiples of a prime number non-prime.
3. Go to the next prime number and make all it's multiples non-prime.

I think you would get a better understanding of the algorithm by reading this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

As for the implementation, just use an array which has all it's elements set to zero, and set the elements from prime number to prime number to one.

Hope this helps!