• 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

    • It gave OEMs all kinds of stuff to put effort into that did nothing about bad drivers that crashed the system.
    • Yes, because Google's ad platform dominates the internet and most sites use Google's ad platform. Microsoft cares about their own ad platform. And they whitelist their ads. Edge is still on mv2 on desktop but they have officially announced they will stop supporting it. They haven't announced the date, but it is on their roadmap. Microsoft HAS the resources to keep it, but they have announced they will remove it unlike other chromium based browsers like Brave and Opera which have announced they will try to keep it. They postponing it in an attempt maybe to gain some market share from Chrome, but their end goal is the same, the deprecation of mv2. https://learn.microsoft.com/en-us/microsoft-edge/extensions-chromium/developer-guide/manifest-v3#manifest-timeline-for-microsoft-edge-and-partner-center
    • I'll say this again:  This hasn't changed since Windows 10.  This customization issue is not unique to Windows 11.   Windows 10 was released about 10 years ago.  I didn't look at changing default fonts in Windows 8 or 7.  Most (sane) people would look for supportability -- you might have the desired customization in those OSs but not able to play games, apps, that one typically gets the OS for.  No one is going to trade off getting an ancient OS just so they can have larger fonts but not be able to play games or run apps.   There are many options that are not exposed in the default UI because they have a lot more potential harm than benefit.  Doesn't mean they don't exist.  Hence, registry changes. "What's the harm by leaving it in Settings?"  Imagine if you changed the default font to something unreadable.  How would you change it back if you can't read anything?  The settings UI allows one to change size and style, but not font, so you'd still be able to read it.  Changing the font itself to Wingdings might render an OS unusable. Now YOU might be savvy enough to make that change and/or undo it, but that's why it's not exposed in simplistic UI and instead is moved to registry changes. Your 3rd party app is most likely causing conflict with the registry as it wants to make its own changes.  It's not voodoo magic here, that's typically what these apps do.  I'd bet you a beer if I spin up a new VM for Windows 11 and try my links above with no Winaero Tweaker it'd work just fine.  Introduction of 3rd party apps is always suspect -- who knows what else it's doing.  
    • Yes, and the reason is the defaults is has. The masses have no interest to change settings etc. It feels cluttered by default. The default home/NTP feels cluttered with so much stuff from MSN. The sidebar has too many buttons with Microsoft services. The default search engine is Bing. Just compare Edge defaults with Chrome defaults. The masses open Edge or are "forced" to open it, they don't like what they see and close it and go back to Chrome.
    • PrivaZer 4.0.106 by Razvan Serea PrivaZer is a PC cleaner that helps you master your security and freedom at home and at work. PrivaZer permanently and irretrievably erases unwanted traces of your past activity on your computer and on your storage devices (USB keys, external drive, and so on) which prevents others from retrieving what you have done, watched, streamed, visited on internet, freeing up valuable hard disk space, and keeping your PC running secure. PrivaZer key features: Deep Cleaning: PrivaZer thoroughly cleans your PC by removing unnecessary files, traces of activity, and potential privacy risks. Advanced Scan Modes: With multiple scan modes, including Quick and Deep scans, PrivaZer ensures comprehensive cleaning tailored to your needs. Customizable Cleaning: PrivaZer allows you to customize cleaning settings, so you can choose exactly what to clean and what to keep. Privacy Protection: PrivaZer safeguards your privacy by securely erasing traces of your online and offline activities, including browsing history and temporary files. Secure File Deletion: PrivaZer securely deletes sensitive files beyond recovery, ensuring your confidential data remains private. Startup Manager: PrivaZer helps you control which programs launch at startup, improving boot times and overall system performance. Automatic Updates: PrivaZer regularly updates its cleaning algorithms to adapt to new threats and ensure effective protection. Scheduled Cleanups: PrivaZer offers the convenience of scheduling automated cleanups, so your PC stays optimized without manual intervention. Portable Version: PrivaZer offers a portable version, allowing you to carry it on a USB drive and clean any PC without installation. Detailed Reports: PrivaZer provides detailed reports after each cleanup, giving you insights into the space reclaimed and the areas cleaned. File Shredder: PrivaZer includes a file shredder feature to securely delete files, making data recovery impossible even with specialized tools. Context Menu Integration: PrivaZer integrates with the context menu, enabling quick and easy access to cleaning functions from any file or folder. Multi-Language Support: PrivaZer supports multiple languages, making it accessible to users worldwide. Automatic Traces Detection: PrivaZer automatically detects traces of activity on your PC, ensuring thorough cleaning without manual intervention. System Restore Point Creation: PrivaZer creates system restore points before cleaning, allowing you to revert changes if needed. Disk Health Analysis: PrivaZer analyzes disk health and alerts you to potential issues, helping you prevent data loss and maintain system stability. Browser Extensions Cleanup: PrivaZer cleans up browser extensions and add-ons, improving browser performance and security. File Association Management: PrivaZer helps you manage file associations, ensuring files open with the correct programs for optimal usability. Intuitive User Interface: PrivaZer features an intuitive user interface, making it easy for both novice and advanced users to optimize their PCs for better performance and privacy. PrivaZer 4.0.106 changelog: New cleanup : BAM (Background Activity Monitor) Improved cleanup : Clipboard Improved UI Download: PrivaZer 4.0.106 | Portable PrivaZer ~30.0 MB (Freeware, paid upgrade available) View: PrivaZer Home Page | Screenshot Get alerted to all of our Software updates on Twitter at @NeowinSoftware
  • Recent Achievements

    • Dedicated
      Epaminombas earned a badge
      Dedicated
    • Veteran
      Yonah went up a rank
      Veteran
    • 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
  • Popular Contributors

    1. 1
      +primortal
      481
    2. 2
      +FloatingFatMan
      264
    3. 3
      snowy owl
      232
    4. 4
      ATLien_0
      231
    5. 5
      Edouard
      172
  • Tell a friend

    Love Neowin? Tell a friend!