• 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

    • I had to turn it off a long time ago on my work machine because virtual desktops were brutal when switching. Big thread about it on Microsoft forums. With animations off it's instant. Sucks as I had to uninstall Deskscapes as it requires animations but on my work machine productivity takes precedence.
    • Even though this tweak is basically just a placebo, I still find myself using it fairly often. There are better options out there, but the CrapFixer app https://github.com/builtbybel/CrapFixer is useful for testing and restoring the original state if needed
    • That’s such a heartwarming story — it really shows the strong sense of community Waffle House is known for. If anyone’s curious about what they offer or planning a visit, you can see full menu with updated prices and calories for 2025.
    • I'm not sure I would really call that a hidden setting, and it's been around since Windows XP.
    • Main server is my old gaming PC from years ago.  It was an older AMD Phenom based desktop until last year when I "upgraded" it.  It hosts Nextcloud, Minecraft, Jellyfin and my personal website, and serves as a general purpose backup NAS.  It is apparent in this picture though it needs a good dusting. Operating System: Debian GNU/Linux (stable, but with backports kernel) CPU: AMD FX 8370 GPU: AMD Radeon RX 480 8GB (Used for hardware transcoding in Jellyfin) Memory: 16GB Corsair Vengeance DDR3 @ 1,866 MT/s Boot Drive: Western Digital Blue 500GB SATA SSD Mass Storage: 4 12TB Western Digital Gold HDDs.  Am using mdadm software RAID 5, with an encrypted LUKS/ext4 filesystem on the array.  My "off site backup" is 3 external drives in an encrypted software RAID 0 that I keep stored outside the house and bring in once a month to sync with the internal drives. Storage drive layout: mdadm -> LUKS -> ext4 Secondary server is a Raspberry Pi 4B that hosts PiHole and Wireguard via PiVPN.  I largely use the PiHole not just for ad blocking, but for parental controls on the kids.  I'm actually thinking of upgrading this to an x86 mini PC so I can get secure boot, SMART monitoring of the boot drive, etc. Router is a GL-iNet Flint 2, incoming internet connection is 1Gbps up, 1Gbps down, no data caps.  Fiber to my service pole then ethernet from there into the house. UPS is an APC Back-UPS XS 1500G.  I've had it for ages and had to replace the battery a few times.  The main server monitors it since our power is pretty unreliable (see screenshot) here in eastern Kentucky.  On the occasion the batteries run down the main server will automatically log into the Pi and do a graceful shutdown on it as part of its power down procedure.
  • Recent Achievements

    • First Post
      Johnny Mrkvička earned a badge
      First Post
    • Week One Done
      viraltui earned a badge
      Week One Done
    • One Month Later
      serfegyed earned a badge
      One Month Later
    • Dedicated
      firey earned a badge
      Dedicated
    • Dedicated
      fettermanj earned a badge
      Dedicated
  • Popular Contributors

    1. 1
      +primortal
      656
    2. 2
      ATLien_0
      224
    3. 3
      Michael Scrip
      224
    4. 4
      Xenon
      146
    5. 5
      +FloatingFatMan
      143
  • Tell a friend

    Love Neowin? Tell a friend!