• 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

    • The new official logo of the GOP
    • Linux 6.16-rc1 is out: What's new and what does it mean for your system? by Paul Hill Linus Torvalds, head and founder of the Linux kernel, has announced the closure of the merge window where major new features are added to the kernel, and the beginning of the Linux 6.16 release candidates, beginning with release candidate 1 (Linux 6.16-rc1). Linux 6.15 was released two weeks ago and in the time since, developers have had the opportunity to try and get their new kernel features into the Linux 6.16 kernel. Over the next two months, we will get seven or eight release candidates where developers will stabilize new and existing features. This means that the stable version of Linux 6.16 will arrive around the end of July. Torvalds said that the merge window seemed pretty normal this time, but did say he had a feeling that there were more “late straggler” pull requests than is typical. Despite this, everything seems to be fine and the schedule will be going forward as planned. Key areas of development Torvalds explained that around half of the changes in the first release candidate were driver updates, with the bulk of those being made up with by GPU and networking drivers. For end users these are the most important changes because when your favorite distribution of Linux ships a new release with this kernel, it will support more graphics cards and networking equipment like Wi-Fi cards. The non-driver updates in this version are split between architecture-specific updates, documentation and tooling (perf tool and selftests), and core changes to filesystems, core kernel, memory management, and networking. Torvalds said the core changes include some of the “most important” changes, though they’re not necessarily major changes. Fixes to the core ensure a more stable Linux kernel for end users, plus better performance. The merge window saw developers submit thousands of non-merge commits and merges. The non-merge commits were around 13,000 while the merge commits nearly reached 1,000. There were 1,783 unique authors submitting code during this window. Next steps Over the coming weeks, Linux developers, including individuals or representatives of companies, will submit bug fixes for new and existing features. This release candidate cycle will run until around the end of July and then the final version will become available. End users shouldn’t go out and download Linux 6.16 when it’s released, instead just wait for your Linux distribution to update to it, as distribution-specific changes get made. Neowin will be following these releases and reporting on any interested changes that are noted. Source: LKML
    • There was no cancelation. Microsoft delayed work on it to focus on further tuning the OS and improving the OS experience overall, before going full core into a direct hardware battle with their partners.
    • As someone who has 500+ hours of playtime on Anno 1800, all I can say is shut up and take my money.
  • Recent Achievements

    • Week One Done
      Al_ earned a badge
      Week One Done
    • Week One Done
      MadMung0 earned a badge
      Week One Done
    • Reacting Well
      BlakeBringer earned a badge
      Reacting Well
    • Reacting Well
      Lazy_Placeholder earned a badge
      Reacting Well
    • Dedicated
      Epaminombas earned a badge
      Dedicated
  • Popular Contributors

    1. 1
      +primortal
      474
    2. 2
      +FloatingFatMan
      273
    3. 3
      ATLien_0
      242
    4. 4
      snowy owl
      210
    5. 5
      Edouard
      182
  • Tell a friend

    Love Neowin? Tell a friend!