• 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

    • There's absolutely nothing in the WINE license preventing this. Regardless if that sentiment is held by the developers of WINE, it likely doesn't concern the people making Proton nor does it prevent them from adding the support.
    • Multiple competing launchers are unironically a gem on PC gaming—I'm not sure why people don't get that yet. Why replicate Apple's horrible control here? Multiple launchers = multiple stores → lower prices for multi-launcher games Every other con seems minute and irrelevant to a vibrant marketplace where you actually save money. The only real complaints I hear are multiple launchers idle as background tasks + people don't like opening multiple apps. For #1, maybe this OS-based launcher should do shutdown idle launchers like GOG. For #2, virtually all launchers let you create shortcuts. Voila, problem solved.
    • Xbox June Update brings unsynced save management, publisher browsing, and more by Pulasthi Ariyasinghe June has been a busy month for Microsoft, bringing major software upgrades across its product stack. It even announced new hardware for its Xbox lineup, finally entering the handheld gaming space. The company's roundup for this month's new features has now been published, and it's touting a great deal of changes. To start off on the PC side, the Xbox app on the platform now has a section to browse by publishers. The company says that this will let players easily discover more games made by their favorite developers and franchises. Copilot for Gaming also landed in beta form recently, letting users ask AI for help when a game gets too difficult. It's only available for iOS and Android for now, with ROG Xbox Ally support coming later this year. Another feature that will hit the Xbox Ally is the new universal launcher feature for the Xbox app on PC. Microsoft just kicked off Xbox Insider testing for this functionality earlier today. Get all the details here. Over on consoles, the ability to hide system apps, pin favorites to the list, and reduce the number of tiles displayed are now available. Game Hubs also arrived as a fresh feature to easily display relevant information when selecting a game to play, offering data on player stats, achievements, friends currently playing, recent captures, available add-ons, events, and more. Double-tapping the play button will quick-launch the game instead. On both Xbox consoles and in the cloud, a new progress bar will now appear when a save has been left behind on a device in an offline state. "A new progress bar, device names, timestamps, and additional details are now displayed when you have previous game saves on another device in an unsynced state," says the company. Microsoft has also added mouse and keyboard controls as well as touch controls for more cloud games this month. These join the fresh additions that have landed on the 'Stream your own game' collection and the Retro Classics app. Check out the full lists on the announcement page here. On top of all this, Microsoft has also announced that Xbox will be at Gamescom this year. While no details have been announced yet, more announcements from Xbox Game Studios may happen at the major gaming event.
    • Hopefully this is a precurser to them linking other launchers to the Xbox console. With this current gen the Xbox has had dismal sales compared to the competition. If they did support Steam, Epic, Ubisoft Connect, etc etc they'd crush on the next gen battle.
    • My update. Didn't see much point in the top panel since global menu isn't there, so going with a win/kde layout now. Overall, I would say Gnome is a disappointment - it's been 15 years and you still have to rely on a bunch of extensions to get anything useful out of it. At the same time, the way Universal Blue / Bluefin is approaching the desktop feels like what Ubuntu should have started doing five years ago (no wonder the guy I learned about this from used to work for Canonical). Maybe I should have gone with Aurora (the KDE variant), or Bazzite with KDE, but I think I have Gnome where it works for me now.       
  • Recent Achievements

    • Dedicated
      Camlann earned a badge
      Dedicated
    • Week One Done
      fredss earned a badge
      Week One Done
    • Dedicated
      fabioc earned a badge
      Dedicated
    • One Month Later
      GoForma earned a badge
      One Month Later
    • Week One Done
      GoForma earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      647
    2. 2
      Michael Scrip
      225
    3. 3
      ATLien_0
      220
    4. 4
      +FloatingFatMan
      144
    5. 5
      Xenon
      136
  • Tell a friend

    Love Neowin? Tell a friend!