Stuck on how to store the highest prime number

This is a discussion on Stuck on how to store the highest prime number within the C Programming forums, part of the General Programming Boards category; Hey all, Basically, I am suppose to compute 10 numbers and find their highest prime number for each of them. ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    3

    Stuck on how to store the highest prime number

    Hey all,

    Basically, I am suppose to compute 10 numbers and find their highest prime number for each of them.

    I've already have the inputs working, and set up 2 arrays to store inputs and their highest prime number. But I am uncertain on how to find and store their highest prime number. Can anyone give me an idea how to start it off?

    Thanks.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Welcome to the forum, Sizz!

    How large are these numbers - can you hold them in an int array?

    Do you have a run-time requirement (maybe 5 or 10 seconds) or no time limit? Trial by division method is easy, but slow. Sieve of Eratosthenes is much faster, and not much harder at all. If the numbers aren't too large, the Sieve of E. would be perfect for this job.

    Read up on the Sieve of Eratosthenes on Wikipedia, and see what you think.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    3
    Hey Adak,
    No, I don't have a runtime requirement. I think my main problem is, if i input 10 numbers, I need to find all the prime numbers from each input i make. Is there an efficient way of doing this??

    Oh and thanks for the suggestion on wikipedia, its quite good .

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    So by "compute" do you mean to "factorise"?
    If that's not correct then you'll need to explain yourself better.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Regardless of what "compute" means, the method of storing a prime value depends on the magnitude of that prime value. I certainly have no idea what "compute highest prime for a value" means, and won't even speculate.

    Virtually all C compilers support a long unsigned type, which is able to represent any integral value between zero and 4294967295. Most modern compilers support a long long unsigned type, which is guaranteed able to represent any integral value between zero and 18446744073709551615. If you need a larger prime value than that, or you have an older compiler that does not support long long types, then you need to find an alternative approach.
    Right 98% of the time, and don't care about the other 3%.

  6. #6
    Registered User
    Join Date
    Feb 2013
    Posts
    3
    Ahhhhhhh sorry for the confusion. I meant "input" instead of "compute".

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Sizz View Post
    Hey Adak,
    No, I don't have a runtime requirement. I think my main problem is, if i input 10 numbers, I need to find all the prime numbers from each input i make. Is there an efficient way of doing this??

    Oh and thanks for the suggestion on wikipedia, its quite good .
    OK, so your program will be taking input for 10 numbers, and needs to find the largest prime number less than each of those 10 numbers, is that right?

    So if the first number is 18, you need the prime number 17 as the answer?

    If so, I'd put the 10 input number into a small array, and sort them, in ascending order (small...big). Now you're set to use the Sieve of Eratosthenes, because it finds ALL the prime numbers as it works - and every time it passes the value of inputNumbers[i], you have your answer for the next input number at primeNumber[i-1].

    Code:
    //inside the Sieve of E.:
    
    
    
    if(primeNumber[i] > inputNumber[j]) {
         printf("Next answer is: %d \n",primeNumber[i-1]);
         increment j; //inputNumber[] index
    }
    increment i; //primeNumber[] index
    The primeNumber[] array is the primeNumbers you have found as the Sieve of E, works. You could do this loop and if() statement either inside the Sieve, or just have the Sieve work until it finds all the primes less than the highest number, and then use the above logic inside a second loop, outside the Sieve.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    Quote Originally Posted by Sizz View Post
    Ahhhhhhh sorry for the confusion. I meant "input" instead of "compute".
    This still leaves us guessing about the rest of it. We aren't mind readers. Lets not play 20 questions with this one.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 11-04-2011, 01:16 PM
  2. HELP: Exclude the highest and lowest number...
    By Ocin101 in forum C Programming
    Replies: 12
    Last Post: 07-21-2009, 01:51 AM
  3. The highest Fibonacci number ever calculated
    By dwks in forum C Programming
    Replies: 19
    Last Post: 07-27-2005, 05:57 PM
  4. Replies: 3
    Last Post: 03-29-2005, 03:24 PM
  5. finding highest number entered
    By volk in forum C++ Programming
    Replies: 11
    Last Post: 03-23-2003, 12:22 AM

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