• 0

[C] Testing whether integer is 'Prime' or 'Not Prime'


Question

Basically I've this homework assignment for my beginner C class, I managed to compile the program but am unable to clear the auto-marker (coursemarker)

Any one got some clues as to why?

The program is required to read a user input integer and calculate whether the integer is prime or not prime and output the respective lines as in the code below. An entry of 0 will result in the program exiting.

otXYN.png

Pardon the noob // comments :p

12 answers to this question

Recommended Posts

  • 0

Can you explain the problem better? Are you just talking about the gray box at the end of the code? And when you post code, post the text instead of an image. Or upload the main.c file and I'll remove it with a text or hex-editor.

And a couple comments on the code. You calculate the square-root of "num" with each iteration of the loop; just do it once and store it in a variable. I'm not sure if the compiler optimizes that out or not. Second, all even numbers greater than 2 are not prime; that could help.

  • 0

The algorithm is fine, but this will get you fired:

while (start<(sqrt(num))

sqrt is an expensive calculation, so you don't want to re-compute it each time through the loop. Compute it once, store it in a local variable and use that for the loop condition.

There are plenty of ways to check for primality. For small primes, the fastest way would be to store all known primes in a sorted array and search (using a binary search) for the input number in that array. You could improve your existing algorithm by testing only for odd numbers, since no even number greater than 2 is prime. More advanced methods (efficient for large primes) are based on probabilities. Check out http://en.wikipedia.org/wiki/Primality_test

  • 0

The best way depends on the greatest number that might be tested in a program; it also depends on your tolerance for a false-positive. The Miller-Rabin test is popular; make sure to read the section about making it deterministic. Since the maximum value that may be tested by your program is INT_MAX, you could easily optimize it using the parameters in the Wikipedia article.

  • 0

Oops, I figured out what my error was, the program was looking for continuous user entry till '0' is keyed in. I put a while loop in the main function and ta-da!

Thanks for the help guys, I'm still in the process of refining my code to check for primes.

  • 0
  On 08/03/2010 at 07:25, evo0o said:

I'm still in the process of refining my code to check for primes.

Other than taking the sqrt() function out of the while loop, you really don't need to change anything. Since you're limiting yourself to 32-bit signed integers, the slowest-case scenario for your test is running the while() loop about 46000 times. That will happen quickly on any CPU.
  • 0

Most people don't realize that: (Prime number > 3) % 6 = 1 or 5 always. (% is the operator which gives you the remainder of the division.)

5 % 6 = 5

7 % 6 = 1

11 % 6 = 5

13 % 6 = 1

17 % 6 = 5

... and so on.

The above calculation can be used as a precondition for testing whether a number is prime, because it helps avoid the use of expensive calculations for testing each and every number for primality with the expensive while loop.

You should also consider hard-coding your program for numbers<=3 because 2 and 3 are prime and 0 and 1 are non-prime.

  • 0
  On 09/03/2010 at 01:18, BGM said:

wtf... wouldn't wanna work where you work! :o

It's a minor difference in code but as mentioned about having it that would means that sqrt() is evaluated each time the condition is check when it only needs to be done once. If we're talking about large prime numbers that would mean a lot of extra computation time wasted.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • Tech demos are a declaration of desire, an horizon for what they pretend to put on those boxes call consoles (i still laugh at the poor implementation of Hairworks in W3 when you compare it with the demos)...being made on UE5 doesn't give me any confidence considering how poorly it runs in those things, and CDPR is not a marvel in that aspect neither. And about the game, so far is non existent besides the cinematic trailer. If from the get go they have to justify the whys for the protagonist, you start your narrative with the left foot.
    • Seen a 5090 for just over $3,000 at Best Buy just a couple days ago. It wasn't the sticker price that made me laugh... it's knowing that, for now... that kind of investment that includes drivers that don't work, is a headache no one should have to shell out for. But.. it's not the first time Nvidia has choked on crappy drivers, won't be the last.. so, if you spent a pretty penny on the next gen, hang in there... sure they'll get it right some day here soon.
    • Because they and their 801 partners are hungry for your data, and the web is the best facilitator of everything privacy-violating in this day and age... They want all your non-microsoft account data going to microsoft's servers:
    • Sorry, I found your question odd, that's all 😅.
    • "LOL The IoT version is for embedded systems" LOL. The IoT version is for whatever you want, why are you so stuck up? It's just A NAME. Open your mind, buddy 😅. It's not a different version of Windows, only the licensing model and the support dates change, nothing else. "there no real reason to do that" Everyone has their reasons. You love to use Linux. Why? You have YOUR reasons. Other people will have theirs. I use Windows 11 and Linux on the side. Why? I have my reasons. "No security updates? Who cares!" Many people do, just not you. Why not use a supported OS instead of an unsupported one if you can? LOL. I find it odd that a person that loves Linux and choice/freedom so much has such a hard time understanding why people do things different than him.
  • Recent Achievements

    • First Post
      m10d earned a badge
      First Post
    • Conversation Starter
      DarkShrunken earned a badge
      Conversation Starter
    • One Month Later
      jrromero17 earned a badge
      One Month Later
    • Week One Done
      jrromero17 earned a badge
      Week One Done
    • Conversation Starter
      johnwin1 earned a badge
      Conversation Starter
  • Popular Contributors

    1. 1
      +primortal
      251
    2. 2
      snowy owl
      157
    3. 3
      +FloatingFatMan
      140
    4. 4
      ATLien_0
      140
    5. 5
      Xenon
      128
  • Tell a friend

    Love Neowin? Tell a friend!