• 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

    • qBittorrent 5.1.1 by Razvan Serea The qBittorrent project aims to provide a Free Software alternative to µtorrent. qBittorrent is an advanced and multi-platform BitTorrent client with a nice user interface as well as a Web UI for remote control and an integrated search engine. qBittorrent aims to meet the needs of most users while using as little CPU and memory as possible. qBittorrent is a truly Open Source project, and as such, anyone can and should contribute to it. qBittorrent features: Polished µTorrent-like User Interface Well-integrated and extensible Search Engine Simultaneous search in most famous BitTorrent search sites Per-category-specific search requests (e.g. Books, Music, Movies) All Bittorrent extensions DHT, Peer Exchange, Full encryption, Magnet/BitComet URIs, ... Remote control through a Web user interface Nearly identical to the regular UI, all in Ajax Advanced control over trackers, peers and torrents Torrents queueing and prioritizing Torrent content selection and prioritizing UPnP / NAT-PMP port forwarding support Available in ~25 languages (Unicode support) Torrent creation tool Advanced RSS support with download filters (inc. regex) Bandwidth scheduler IP Filtering (eMule and PeerGuardian compatible) IPv6 compliant Available on most platforms: Linux, Mac OS X, Windows, OS/2, FreeBSD qBittorrent 5.1.1 changelog: BUGFIX: Don't interpret wildcard pattern as filepath globbing (glassez) BUGFIX: Fix appearance of search history length spinbox (glassez) BUGFIX: Remove dubious seeding time max value (glassez) BUGFIX: Fix ratio handling (glassez) BUGFIX: Fix compilation with Qt 6.6.0 (glassez) WEBUI: Make General tab text selectable by default (dezza) WEBUI: Add versioning to local preferences (Chocobo1) WEBUI: Make multi-rename search & replace fields use a monospace font (Atk) WEBUI: Fix wrong replacement sequence in IPv6 string (Chocobo1) WEBUI: Fix memory leak (bolshoytoster) WEBUI: Fix path autofill in set location and new category (tehcneko) RSS: Mark matched article as "read" if it refers to a duplicate torrent (glassez) WINDOWS: Update command line help message (KanishkaHalder1771) WINDOWS: NSIS: Don't require agreement on the license page (Chocobo1) LINUX: Fix preview not opening on Wayland (Isak05) LINUX: Add fallback for random number generator (Chocobo1) Download: qBittorrent 5.1.1 | Portable | ~40.0 MB (Open Source) Download: qBittorrent 64-bit installer (qt6) | 41.7 MB Links: qBittorrent Home page | Screenshot Get alerted to all of our Software updates on Twitter at @NeowinSoftware
    • Linus Torvalds releases a pretty ordinary Linux 6.16-rc3 by Paul Hill Linus Torvalds, the head and founder of the Linux kernel, has announced the release of Linux 6.16-rc3. This release comes with fixes for new features that were introduced during the merge window several weeks ago, and for old features where issues have been detected or improvements need to be made. If you remember last week, Torvalds said that rc2 seemed smaller than usual, putting it down to people going on vacation. He said this week’s rc3 seems to be in the usual ballpark for this time of the cycle, so everything looks “entirely normal.” In terms of changes, this release is “dominated” by wireless networking and GPU driver updates, however, Torvalds doesn’t think that anything really huge stands out this time. While nothing stands out Torvalds urged people to carry on testing and submitting patches. This update saw improvements to the core system and architecture. There have been improvements to ARM64 KVM that improve stability and correctness of virtualizations on ARM64. There are also improvements to RISC-V KVM and Trust Domain Extensions (TDX) for Intel which expand and secure virtualization capabilities on those architectures. On the graphics front, there are fixes for the amdgpu and amdkfd drivers that fix job handling, engine resets, display corruption, and power management features. The driver used for Qualcomm’s Adreno GPUs has been updated to improve fault handling, display timing, and driver binding. The open-source Nouveau (Nvidia) driver has been updated with fixes for GSP message queue references, potential integer overflows, buffer size adjustments, and a use-after-free bug. Finally, the Intel i915 driver has been updated to address early wedge issues, memory initializations, and build errors. There are also improvements to Wi-Fi devices (ath12k and iwlwifi), sound (ALSA), power management on AMD, and file system improvements (OverlayFS, EROFS, XFS, NFS, SunRPC). Linux 6.16 is due for release at the end of July and will then be picked up by Linux distributions, which will be the first interaction most end users have with the new features in this update. The main benefit of a newer kernel is that Linux will work on newer hardware, so if you’ve had issues with Linux, be sure to try it periodically in case your hardware is now supported.
    • Technically, it should be account-bound after activating it
  • Recent Achievements

    • Week One Done
      urbanmopdubai1 earned a badge
      Week One Done
    • One Month Later
      Jim Dugan earned a badge
      One Month Later
    • 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
  • Popular Contributors

    1. 1
      +primortal
      646
    2. 2
      Michael Scrip
      226
    3. 3
      ATLien_0
      219
    4. 4
      Steven P.
      150
    5. 5
      Xenon
      145
  • Tell a friend

    Love Neowin? Tell a friend!