• 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

    • I honestly think this does not make any noticable difference to anyone with a PC with average specs.
    • OpenAI takes down all traces of Jony Ive "io" deal following court order by David Uzondu Early this month, we reported that OpenAI was working on a mobile gadget in the form of a screenless, wearable device, born from a newfound partnership (friendship?) between renowned former Apple designer Jony Ive and OpenAI CEO Sam Altman. The announcement came with a video that had the two men talking about the future of technology. Well, that video has now been made private on YouTube, and the original announcement page has been taken down. The whole thing is on pause because of a simple trademark dispute. OpenAI was forced to pull the materials following a court order. If you visit the original announcement page, it now says: Despite the legal hassle over the name, the actual business deal seems safe. According to Bloomberg's Mark Gurman, the acquisition itself is unaffected by the complaint. So, who is iyO (pronounced eye-oh), the other party in this mess? If the name sounds unfamiliar, its background will not. This iyO company is an independent startup that graduated from X, Alphabet's moonshot factory, and yes, that is the same Alphabet, the parent company of Google. iyO claims to be on a mission to bring "natural language computing" to the masses. A quick look shows two products listed on its website: the Vad Pro, a high-end wired audio device for professionals, and iyO One, a set of AI-powered earbuds the company is calling the "world's first audio computer." A judge reportedly found its trademark lawsuit against OpenAI credible enough to issue the restraining order, suggesting the ChatGPT creator's video could create genuine consumer confusion between the two similarly named ventures.
    • I've set since XP - Best performance in the Performance settings. 11 included. I enable only the show shadows after that, so I can see better fonts and mouse.. But hardly I can say I can see a difference today.
    • Yeah this kinda means nothing to me if it's going to be the same mess as HDMI 2.1 where it was difficult to know what features you were getting. It was way too confusing, designed to fool us into thinking we was getting something better with the higher number when a lot of the times we didn't get anything better because companies can add and remove features at will, which if that is the case for 2.2, then who cares lol.
    • Someone wrote a script to block 'brainrot' content online using an $8 smart plug by Usama Jawad Original image via Neil Chen Many people use smart plugs nowadays due to the various advantages they offer, including automation, integration with mobile software, increased home security, better energy efficiency, and compatibility with other smart products. However, a smart plug customer has gone a step further by enhancing their hardware in a way that it blocks them from viewing "brainrot" content online, or any website, for that matter. As seen in a popular thread over on Hacker News, a person known as "NWChen" has written a script that connects to the $8 Kasa Smart Wi-Fi Plug Mini and utilizes it to restrict access to websites of your choice. In essence, this plug then acts as a physical switch that you can toggle to visit certain websites. NWChen's main motivation behind this initiative was to avoid brainrot, with examples listed as X (formerly known as Twitter), Instagram, YouTube, and Reddit in their blog post. In terms of technical functionality, the smart plug connects to Wi-Fi (obviously) and hosts a physical switch that can be used to turn it on and off. NWChen's script connects to the smart plug via an API and then polls its state. If it's on, websites of your choice get restricted and you can't open them anymore, until you physically get up and turn off the plug, or remove the website from you blocklist. NWChen has recommended plugging in the hardware far away from you so there is sufficient resistance in turning off the plug. In the thread, many have praised this invention, believing that the nature of this mechanism provides enough hurdles where you'd rather just not visit the problematic websites anymore. However, some have noted that "those without self control cannot be trusted if they hold the switch". Some have also highlighted a problem where a user can simply stop the script's execution without much friction. Overall, it's a fairly interesting setup, even if it's fairly rudimentary in nature. Configuring this physical block with a Kasa smart plug is fairly easy. You can simply download the script from the laptop-brick GitHub project here, install it, get the IP address of your smart plug, and then use it when you're executing the script. You can modify the blocklist using a dedicated file present inside the GitHub project.
  • Recent Achievements

    • Conversation Starter
      Brett76 earned a badge
      Conversation Starter
    • One Month Later
      Miguel Batista earned a badge
      One Month Later
    • Dedicated
      moojay67 earned a badge
      Dedicated
    • One Month Later
      Jim Dugan earned a badge
      One Month Later
    • First Post
      Johnny Mrkvička earned a badge
      First Post
  • Popular Contributors

    1. 1
      +primortal
      655
    2. 2
      Michael Scrip
      229
    3. 3
      ATLien_0
      220
    4. 4
      Steven P.
      150
    5. 5
      Xenon
      143
  • Tell a friend

    Love Neowin? Tell a friend!