• 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

    • Apple Intelligence can now analyze your iPhone's screen, offers live translation by Aditya Tiwari Alongside iOS 26, iPadOS 26, macOS 26, watchOS 26, tvOS 26, and new AirPods features, Apple announced some stuff for Apple Intelligence at WWDC 2025. A highlight of the latest announcements is that developers can now access Apple's on-device foundation models, which power Apple Intelligence, to enhance their apps. Apple's Foundation Models framework enables developers to create AI-powered features and experiences that can also operate offline. "The framework has native support for Swift, so app developers can easily access the Apple Intelligence model with as few as three lines of code," Apple said, adding that the access is offered free of charge. Apple has introduced several new features for the general public. For starters, the new Live Translation feature works across Messages, FaceTime, and phone calls, using "Apple-built models that run entirely on device" to translate messages from one language to another. In other words, the feature can translate written text in Messages into the recipient's preferred language and display translated live captions while still hearing the speaker’s voice in FaceTime. Meanwhile, the translated text is spoken aloud on regular phone calls throughout the conversation. Visual Intelligence can now access a user's iPhone screen to answer questions and take action on the content being viewed on the screen across apps. Users can ask ChatGPT for details on specific objects and what they're looking at on their screen to learn more. They can also search Google, Etsy, and other supported apps to find similar images and products. Visual Intelligence can also identify events displayed on the screen and suggest adding them to the user's calendar. The updated Genmoji feature lets users mix emojis and combine them with text descriptions to generate something new. They can change expressions and adjust personal attributes, such as hairstyle, to match the latest look when making Genmojis inspired by their friends and family members. Image Playground has been updated to support new styles generated by ChatGPT, such as oil paintings or vector art. When users have a specific idea in mind, they can use the "Any Style" option. Apple Intelligence also powers the Shortcuts app, using on-device processing or Private Cloud Compute to generate responses that feed into the rest of the shortcut while maintaining privacy. For instance, Apple explained that "a student can build a shortcut that uses the Apple Intelligence model to compare an audio transcription of a class lecture to the notes they took, and add any key points they may have missed." Apple is integrating its AI features into more apps with subsequent OS updates. The Wallet app can now summarize order tracking details from emails sent by merchants and delivery carriers. It lets users check their full order details, progress notifications, and other details. In Messages, Apple Intelligence can suggest where a poll might come in handy, and users can create backgrounds to fit their chats using Image Playground. The new Apple Intelligence features are available for testing on iPhone, iPad, Mac, Apple Watch, and Apple Vision Pro through the Apple Developer Program. By the end of the year, Apple's AI suite will support more languages, including Danish, Dutch, Norwegian, Portuguese (Portugal), Swedish, Turkish, Chinese (traditional), and Vietnamese. You can read about Apple Intelligence in the official announcement post on Apple Newsroom.
    • Absolutely. Glass widgets, tabs, docks, Rainmeter, MicaForEveryone (gorgeous full glass explorer windows), etc. some of us never left the glass ecosphere. I actually hope this encourages MS to put those Acrylic/Mica/Glass hooks back into the OS as an option. It doesn't have to be the default, but some of us would love the choice.
    • I had deleted the folder after installing the update and then re-created the inetpub folder. Ran the script today even though the folder exists, it does some minor changes to the permissions and to the order of some.
    • Creating 1,250 jobs...in order to destroy two orders of magnitude more.
  • Recent Achievements

    • Rookie
      CHUNWEI went up a rank
      Rookie
    • Enthusiast
      the420kid went up a rank
      Enthusiast
    • Conversation Starter
      NeoToad777 earned a badge
      Conversation Starter
    • Week One Done
      VicByrd earned a badge
      Week One Done
    • Reacting Well
      NeoToad777 earned a badge
      Reacting Well
  • Popular Contributors

    1. 1
      +primortal
      471
    2. 2
      +FloatingFatMan
      268
    3. 3
      ATLien_0
      256
    4. 4
      Edouard
      200
    5. 5
      snowy owl
      180
  • Tell a friend

    Love Neowin? Tell a friend!