Finding primes

[scwizzo]

I'm trying to find all primes below a certain number, which is the square root of some original number. By finding all the primes below the original numbers square root and dividing the original by the found primes, you can tell if the original number is prime (for people that didn't know that). So... here is my function to find all the prime numbers below a certain number. However, I am getting a runtime error and the program needs to close whenever I try it. I'm not quite sure on what is happening, and maybe I've stared at it too long. Does anyone see anything that is either out of bounds, a problem, or a fix etc.

bool FindPrimes(int upper, int values[]) //upper needs to be square root of the original number
{
    int index = 0, pRet = 1, loop = 0, ret = 0;
    bool bRet = true; //automatically assume first number is prime, which is 2 anyways
    for(loop = 2;loop <= upper; loop++){ //start the loop at 2 since it is the first prime
        bRet = true;
        for(int i = 0; i <= index; i++){
            ret = loop &#37; values[i]; //check if there are any remainders, remainder = 0 means not prime
            if(ret == 0){
                bRet = false; //the value was not prime
                break;
            }
        }      
        if(bRet){
            values[index] = loop; //add the loop value to the array of int's if it is not divisible by any prime thus far
            index++; //increase the index count
        }
    }
    return true;
}

[tabstop]

We start with i = 0, so we do ret = loop % values[0]. If values[0] happens to be zero....

[scwizzo]

I initialize values[0] to be equal to 2 before i call the function, so that exact thing doesn't happen. But I will agree it's something with that line cause I can comment it out and it will not terminate or fail. I also tried putting i < index instead of <= and it didn't solve anything.

v[0] = 2;

FindPrimes(sqPrime,v);

[tabstop]

In that case, I would next check that values is a large enough array to store all the numbers you're trying to store in it.

[phantomotap]

What exactly is this supposed to do? Seriously, what are you setting the elements of the 'values' array to before the function is called? Zero? One? Successive Primes?

I only ask because it looks as if it will do nothing unless the 'values' array is pre-filled with the correct values.

When faces with a problem related to algorithm implementation get yourself a pen and paper and run through your algorithm manually.

Soma

[scwizzo]

I made v[9999] and the square root of the number i picked is only like 3200, so there is definitely enough space. I only filled v[0] = 2, the rest from 1-9999 is not filled. Should that be fixed or does it not matter? The only reason I set v[0] = 2 is so it has a starting place to decide if the next number is prime, which is 3, and it is, so it should add it to v[1] = 3 like so, then go to 4 and its not prime so go to 5, prime, add to v[2] = 5. It's obviously something to do with the modulus cause i can comment it out and it will work fine minus the actual "adding primes to array" part.

[master5001]

To what end? I do not see any particular utility behind doing things this way.

[scwizzo]

To what end? I do not see any particular utility behind doing things this way.

Huh?

[master5001]

Typically, if you need a list of primes, for example you would generate a list of prime numbers. Not just generate a list of arbitrary data and determine if that arbitrary data is prime. Your way seems like it will produce random effectiveness.

[tabstop]

Ooh! Try switching "index++" and "values[index] = loop".

[scwizzo]

This is more of my own doing and just messing around. There is no real usefulness in what I am trying to achieve other than maybe get a list of primes. But I don't see how this is random if it goes through a process of checking each number. Unless you mean the fact that I'm finding all the primes below a number, then checking another number using those primes. I know this probably isn't the most effective way to find primes, but it works for me right now.

[scwizzo]

Ooh! Try switching "index++" and "values[index] = loop".

I just caught that right before you replied. Instead of switching them I put int index = 1, and i < index instead of i <= index. It works now. Thank you!