• 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

    • Maybe you don't realize this...but everything you said agreed with me. Yes, many tech outlets reported on Ryzen 9000 issues prior to 24H2, which I already addressed, and as I already said, that issue only existed for a few short months. Ryzen 9000 was released the same quarter of 2024 as 24H2. So again...months, not years. I also already said 24H2 showed some minor improvements on older Ryzen CPU. The article you posted agrees with me, and even says the improvements were only 3-5%, which is even more harsh a statement than what I said. If you want to fuss on the 3-5% numbers, then yes, I will grant you that was an issue for an extended amount of time. In my opinion, that is such a small amount it isn't worth fussing over, but you are welcome to a different option. However, if that was your point, then you didn't make that point in good faith, because you highlighted Ryzen 9000 so much, which had a FAR bigger and FAR shorter issue, it's really a very different conversation.
    • The vast majority of users do not care which iOS version they're using. They don't even know or bother updating to the latest version, unless they see the prompt. The version numbers is more for the power users and I don't think Apple renamed their OS for them.
    • No operating system works well with programs that modify its interface. There will always be bugs, whether it's MacOS or Linux. Windows too, you'll only suffer from bugs using this crap software.
    • KDE brings UI improvements, bug fixes and more to Plasma 6.4 as stable release draws near by David Uzondu With less than a month to the release of Plasma 6.4, the KDE dev team has shared what it has been working on in the latest issue of its weekly roundup. The update shows a heavy focus on user interface polish and a whole slew of bug fixes as the June 17 release date gets closer. The team has pushed a number of UI refinements for the upcoming version. On the System Settings page for Wi-Fi, the network list can now be fully navigated with a keyboard. KDE also disabled the ability to drag and drop displays on top of one another in the monitor settings. This was done because it could create unsupported arrangements that triggered a cascade of strange bugs throughout the system. Waking up a sleeping computer by pressing the power button no longer causes the bizarre logout screen to appear after you unlock it, which is a relief. Alignment issues in the settings page for the Digital Clock widget were also resolved. The list of bug fixes for 6.4 is extensive. The development team has fixed the most common crash affecting the System Monitor and squashed another one related to a divide-by-zero error. For users with multiple monitors, a long-awaited fix has landed that prevents windows from disappearing when the screen they are on gets disconnected. Even the humble Sticky Notes widget received attention; it will no longer freeze the Plasma shell if you place it on a very thick panel. Discover, the software center, also had a bug patched that caused it to crash if closed too quickly after launch. Here's the full list of improvements: Putting a Sticky Note widget on a very thick panel can no longer cause Plasma to freeze; now, you can use a thick panel with a sticky note on it as a notes sidebar. Fixed the most common System Monitor crash. Fixed another crash in System Monitor, this time a divide-by-zero. Fixed a case where xdg-desktop-portal-kde could crash after you choose a video source to start streaming. Fixed a bug that caused Discover to crash if you close it immediately after it launched. Fixed multiple subtle bugs with the screen chooser widget and OSD that caused it to do the wrong thing on rotated screens or when mirroring screens. Fixed a bug that caused the System Settings’ search field not to be focused properly when pressing Ctrl+F while any UI elements in a settings page already had focus. Fixed the root cause of multiple issues involving windows disappearing when you disconnect the screen they’re on. Clicking a button on a desktop widget that opens a menu no longer inappropriately makes the widget enter Widget Edit Mode. Files with a # or ? character in their name or full path are no longer unexpectedly missing from the history lists in Kicker/Kickoff/etc launchers. Fixed a bug that caused the screen chooser window to sometimes not appear as expected when OBS was launched. Fixed a bug that caused tiled windows on a multi-screen setup to lose their tiling settings when the system went to sleep and woke up again. The "Move window to [activity]" feature now works properly when invoked from the Task Manager widget. Fixed a bug in the Kicker Application Menu that caused keyboard navigation not to work if the popup opened with an item under the pointer. In the Overview effect’s grid view, dragging windows tiled on one virtual desktop over to a different virtual desktop now keeps them tiled as expected. The focus may be on the imminent 6.4 release, but work on what comes next never really stops. Looking ahead, development on Plasma 6.5 is already well underway. Just last week, the KDE team brought several performance improvements to Plasma 6.5.0. This week, the team fixed a nagging bug that sometimes caused the Networks widget to think a hotspot was still enabled after disconnecting from Wi-Fi. On the features side, the System Settings' Fonts page now prevents you from breaking your system entirely by setting fonts below 4pt. In addition to that, switching time spans in the Info Center’s energy page now features smooth graph animations. Performance-wise, kwriteconfig should also be faster, allowing changes you made to the keyboard layout using the tool to reflect immediately.
  • Recent Achievements

    • Week One Done
      abortretryfail earned a badge
      Week One Done
    • First Post
      Mr bot earned a badge
      First Post
    • First Post
      Bkl211 earned a badge
      First Post
    • One Year In
      Mido gaber earned a badge
      One Year In
    • One Year In
      Vladimir Migunov earned a badge
      One Year In
  • Popular Contributors

    1. 1
      +primortal
      495
    2. 2
      +FloatingFatMan
      252
    3. 3
      snowy owl
      252
    4. 4
      ATLien_0
      228
    5. 5
      +Edouard
      191
  • Tell a friend

    Love Neowin? Tell a friend!