• 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

    • Until EVs get solid state batteries that can last 800miles+ on a single charge in Canada's -50°C weather, all while functioning 100% offline, they're still just at a guineapig testing stage IMO, and simply not worth purchasing...
    • I would question if Neowin really needs science research studies/stories than.
    • Microsoft reveals Mu, an on-device small language model built into Windows 11 by Pradeep Viswanathan Last year, Microsoft revealed Copilot+ PCs featuring a dedicated Neural Processing Unit (NPU) capable of over 40 TOPS or more. These Copilot+ PCs came with Phi-Silica, an on-device SLM to bring language intelligence capabilities to Microsoft's own first-party apps and apps from other 3rd-party developers. Today, Microsoft revealed Mu, a new on-device small language model built into Windows 11. Microsoft's goal was to create an AI-powered agent within the Settings app that can understand a user's natural language queries and integrate it into the existing search box for a smooth user experience. Hence, Microsoft is using the new Mu model to power the new agent feature in the Settings app, which was made available to Windows Insiders recently in the Dev Channel with Copilot+ PCs. Like Phi-Silica, Mu is designed to operate efficiently on NPUs, delivering over 100 tokens per second while running locally. In the official blog post, Microsoft explained how they designed and trained the Mu language model. Here's an overview of the Mu language model: Mu is a 330M encoder-decoder language model. The encoder-decoder approach achieved about 47% lower first-token latency and 4.7× higher decoding speed compared to a decoder-only model of similar size. Mu uses weight sharing in certain components to reduce the total parameter count. Microsoft trained Mu using NVIDIA A100 GPUs on Azure Machine Learning. Mu is nearly comparable in performance to a similarly fine-tuned Phi-3.5-mini, despite being one-tenth of the size. The model is better suited for multi-word queries. So for short or partial-word inputs, the Settings app will continue to surface lexical and semantic search results in the search box. Interested users can download Windows 11 Build 26120.3964 (KB5058496) or higher to check out this new AI-powered agent in the Windows Settings app.
    • I work at a company that sends Samsung stuff to Best Buy, Costco, Amazon, and others, we are about to killed after this event.
    • only using AI for science research studies/stories like this which are somewhat separate from our main tech/IT-focused articles, it is like a separate column, sort of like the software stories. Also I believe plenty of other sites use AI in some form of other, but we are also honest enough to disclose it. Btw no that headline was completely me.
  • Recent Achievements

    • Dedicated
      tesla maxwell earned a badge
      Dedicated
    • Dedicated
      Camlann earned a badge
      Dedicated
    • Week One Done
      fredss earned a badge
      Week One Done
    • Dedicated
      fabioc earned a badge
      Dedicated
    • Week One Done
      GoForma earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      632
    2. 2
      Michael Scrip
      224
    3. 3
      ATLien_0
      219
    4. 4
      +FloatingFatMan
      142
    5. 5
      Xenon
      135
  • Tell a friend

    Love Neowin? Tell a friend!