• 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

    • Samsung Electronics has multiple subsidiaries. Samsung Display is a subsidiary that deals in screen manufacturing, it's a supply chain-based company where the staff solely care about manufacturing displays. Samsung Electronic's TV and Phone division may have other priorities, for example Samsung TV didn't want to go in on OLED because margins were lower when building the entire TV. Samsung Display's entire existence however now depends on OLED as they couldn't undercut Chinese LCD manufacturers but could compete against LG Display who is the only competitor in that market. Samsung Display has this screen manufacturing investment, but Samsung Mobile may not be willing to reduce their margins for going with a display technology that eats into the phone margins.
    • The weather looks gorgeous, I love the atmosphere of this new area.
    • Similar to what started me on the path to switching to Linux... for the first 6mo of Win10 it was installing an AMD GPU driver that broke audio over HDMI which was essential to me. Driver from AMDs site was fine.
    • I have avoided many deer, a few moose, and other smaller animals during my years of driving and have managed just fine with only ABS and ESP, both of which can also be problematic depending on circumstance. I have never feared driving and I live in a rural area with a lot of deer and other animals. Winter or summer, heavy rain or sunshine, night or day, I always prefer and like to drive myself, and I drive constantly in my job. People die in accidents and they always will, that is a fact of life. Something like self-driving busses I can advocate for because they can be set to drive on static routes that always stay the same - i.e. those routes can be specially designed and maintained for them. I've already seen enough idiots doing random idiotic things with their Tesla autodrives that I would rather see them crash and burn because of their own stupidity instead of their "computer failing". I've also been a PC and tech enthusiast of over 25 years so I I'm fine with tech but I want to be the one who uses it, and decides how much of it I use. I also do not want it to make my hands, feet and brain obsolete. For me it's not really about if a computer can do it but about people not having to do things themselves (responsibly). I think that basic driving education should be done with a manual car and these "automatic only" cards should not exist (yes, I'm European and we drive a lot of manual cars, I even prefer them). If a person doesn't have enough coordination to manage a steering wheel, shitfer and pedals, how on Earth are they able to react to any unforseen situation on the road? And giving them autodrive doesn't make me feel any better if the person behind the wheel can't manage even basic driving themselves. One of the things I hate most in today's society (in general) is how pretty much everything that is considered even a bit dangerous is eliminated instead of educating people to assess risks and avoid problems themselves. Instead we make brains obsolete by building systems that do everything for us.
  • Recent Achievements

    • One Month Later
      KynanSEIT earned a badge
      One Month Later
    • One Month Later
      gowtham07 earned a badge
      One Month Later
    • Collaborator
      lethalman went up a rank
      Collaborator
    • Week One Done
      Wayne Robinson earned a badge
      Week One Done
    • One Month Later
      Karan Khanna earned a badge
      One Month Later
  • Popular Contributors

    1. 1
      +primortal
      674
    2. 2
      ATLien_0
      274
    3. 3
      Michael Scrip
      219
    4. 4
      +FloatingFatMan
      170
    5. 5
      Steven P.
      161
  • Tell a friend

    Love Neowin? Tell a friend!