• 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

    • Aiarty Image Enhancer for PC & Mac (worth $85) free offer ends today June 8 by Steven Parker Claim your complimentary eBook worth $85 for free, before the offer ends today June 8. Get Aiarty Image Enhancer to restore and upscale images to 32K with more details. Make your images and photos larger, sharper and clearer with AI. Tired of the tiny, blurry or low-resolution images downloaded from web or grainy pictures taken by old smartphones? Aiarty Image Enhancer comes to help you out. Leveraging tailored AI models and deep learning algorithms, it can transform any images, photos and AI arts into high-quality visuals with exceptional clarity and realistic details. No matter you’re enhancing web graphics, restoring cherished family memories, or preparing visuals for creative projects, Aiarty can produce studio-quality results in just a few clicks. Get it now to transform your images to stunning masterpieces at zero cost! Key Features: Upscale: enlarge images and photos to 4K/8K/32K for printing, archiving, sharing, displaying, or more. More details: generate more realistic details for hair, fur, feature, skin textures and so on, ensuring crystal-clear pixels. Restore face with faithful details, perfect for portraits, selfies, old photos, group shot. 4-in-1 enhancement: deblur, denoise, dejpeg and upscale image in one click. Batch process. Enhance 3000+ images at once, streamlining image editing workflow. Fast & Simple. Upscale 100 images in 2 minutes with just one click. No skills needed. Trained on 6.78 million images. Optimized for NVIDIA, AMD, and Intel GPUs & CPUs. The exclusive offer ends on June 8th. Don't miss out – grab your free licensed copy today. How to get it Please ensure you read the terms and conditions to claim this offer. Complete and verifiable information is required in order to receive this free offer. If you have previously made use of these free offers, you will not need to re-register. While supplies last! Download Aiarty Image Enhancer for PC/Mac (worth $85) for free Offered by Digiarty WinXDVD, view other free resources The below offers are also available for free in exchange for your (work) email: Winxvideo AI V3.0 Lifetime License for PC ($69.95 Value) FREE – Expires 6/8 Aiarty Image Enhancer for PC/Mac ($85 Value) FREE – Expires 6/8 Solutions Architect's Handbook, Third Edition ($42.99 Value) FREE – Expires 6/10 AI and Innovation ($21 Value) FREE – Expires 6/11 Unruly: Fighting Back when Politics, AI, and Law Upend [...] ($18 Value) FREE - Expires 6/17 SQL Essentials For Dummies ($10 Value) FREE – Expires 6/17 Continuous Testing, Quality, Security, and Feedback ($27.99 Value) FREE – Expires 6/18 VideoProc Converter AI v7.5 for FREE (worth $78.90) – Expires 6/18 Macxvideo AI ($39.95 Value) Free for a Limited Time – Expires 6/22 The Ultimate Linux Newbie Guide – Featured Free content Python Notes for Professionals – Featured Free content Learn Linux in 5 Days – Featured Free content Quick Reference Guide for Cybersecurity – Featured Free content We post these because we earn commission on each lead so as not to rely solely on advertising, which many of our readers block. It all helps toward paying staff reporters, servers and hosting costs. Other ways to support Neowin The above deal not doing it for you, but still want to help? Check out the links below. Check out our partner software in the Neowin Store Buy a T-shirt at Neowin's Threadsquad Subscribe to Neowin - for $14 a year, or $28 a year for an ad-free experience Disclosure: An account at Neowin Deals is required to participate in any deals powered by our affiliate, StackCommerce. For a full description of StackCommerce's privacy guidelines, go here. Neowin benefits from shared revenue of each sale made through the branded deals site.
    • You will find sketch and clone apps on both the Play Store and the App Store contrary to what Google and Apple will tell you. This fact negates their argument for why there shouldn't be other app stores and so on, it's BS at the end.
    • I ran the powershell script and it did not "recreate the inetpub directory if it has been deleted" I rebooted several times and also tried re running the script. I had to click y three times when I ran it initially as well, now running it just returns to a new poweshell line with no errors but still no directory recreated. meh
    • So? What matters for the masses is the default experience. And in their own ad block implementation they whitelist their ad platform by default. What they care about is making their ad platform more relevant and a good way to do that in their own browser implementation is to blacklist google's platform (lowering its market share) and whitelist theirs (increasing its market share).
    • This, plus loved it as a cameo on 6 underground  
  • Recent Achievements

    • First Post
      viraltui earned a badge
      First Post
    • Reacting Well
      viraltui earned a badge
      Reacting Well
    • Week One Done
      LunaFerret earned a badge
      Week One Done
    • Week One Done
      Ricky Chan earned a badge
      Week One Done
    • Week One Done
      maimutza earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      482
    2. 2
      +FloatingFatMan
      264
    3. 3
      snowy owl
      238
    4. 4
      ATLien_0
      231
    5. 5
      Edouard
      177
  • Tell a friend

    Love Neowin? Tell a friend!