Finding primes

This is a discussion on Finding primes within the C++ Programming forums, part of the General Programming Boards category; I'm trying to find all primes below a certain number, which is the square root of some original number. By ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    416

    Finding primes

    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.

    Code:
    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;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    We start with i = 0, so we do ret = loop % values[0]. If values[0] happens to be zero....

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

    Code:
    v[0] = 2;
    
    FindPrimes(sqPrime,v);
    Last edited by scwizzo; 09-10-2008 at 05:21 PM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,174
    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

  6. #6
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.
    Last edited by scwizzo; 09-10-2008 at 05:59 PM.

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    To what end? I do not see any particular utility behind doing things this way.

  8. #8
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    Quote Originally Posted by master5001 View Post
    To what end? I do not see any particular utility behind doing things this way.
    Huh?

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Ooh! Try switching "index++" and "values[index] = loop".

  11. #11
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

  12. #12
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    Quote Originally Posted by tabstop View Post
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. tools for finding memory leaks
    By stanlvw in forum C++ Programming
    Replies: 4
    Last Post: 04-03-2009, 11:41 AM
  2. Finding primes
    By starripper in forum C++ Programming
    Replies: 19
    Last Post: 01-14-2006, 03:17 PM
  3. MFC :: Finding Child Window of a CWnd* Object?
    By SyntaxBubble in forum Windows Programming
    Replies: 2
    Last Post: 09-06-2003, 09:06 AM
  4. a program that writes the primes
    By Geo-Fry in forum C++ Programming
    Replies: 8
    Last Post: 03-29-2003, 05:37 PM
  5. Finding primes...
    By ER in forum C++ Programming
    Replies: 2
    Last Post: 12-08-2001, 03:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21