C – determine if a number is prime

by

OK, so forget about C. Suppose I give you a number and ask you to determine if it’s prime. How do you do it? Write down the steps clearly, then worry about translating them into code.

Once you have the algorithm determined, it will be much easier for you to figure out how to write a program, and for others to help you with it.

edit: Here’s the C# code you posted:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

This is very nearly valid C as is; there’s no bool type in C, and no true or false, so you need to modify it a little bit (edit: Kristopher Johnson correctly points out that C99 added the stdbool.h header). Since some people don’t have access to a C99 environment (but you should use one!), let’s make that very minor change:

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

This is a perfectly valid C program that does what you want. We can improve it a little bit without too much effort. First, note that i is always less than number, so the check that i != number always succeeds; we can get rid of it.

Also, you don’t actually need to try divisors all the way up to number - 1; you can stop checking when you reach sqrt(number). Since sqrt is a floating-point operation and that brings a whole pile of subtleties, we won’t actually compute sqrt(number). Instead, we can just check that i*i <= number:

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

One last thing, though; there was a small bug in your original algorithm! If number is negative, or zero, or one, this function will claim that the number is prime. You likely want to handle that properly, and you may want to make number be unsigned, since you’re more likely to care about positive values only:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

This definitely isn’t the fastest way to check if a number is prime, but it works, and it’s pretty straightforward. We barely had to modify your code at all!

More Related Contents:

  1. Program to find prime numbers
  2. Most elegant way to generate prime numbers [closed]
  3. Check if number is prime number
  4. How do I implement the Sieve Of Eratosthenes using multithreaded C#?
  5. Prime Factors In C#
  6. C#: How to make Sieve of Atkin incremental
  7. synchronization object [closed]
  8. Generate Every Possible 2 Character Combination [duplicate]
  9. Arithmetic operator overloading for a generic class in C#
  10. Why exactly is void async bad?
  11. How to clear the text of all textBoxes in the form?
  12. Handling ExecuteScalar() when no results are returned
  13. Setting unique Constraint with fluent API?
  14. How to decode string to XML string in C#
  15. Collection of generic types
  16. Sending Outlook meeting requests without Outlook?
  17. TestInitialize vs ClassInitialize
  18. Getting relative virtual path from physical path
  19. BitmapImage to byte[]
  20. Print FixedDocument/XPS to PDF without showing file save dialog
  21. Index of Currently Selected Row in DataGridView
  22. Use different name for serializing and deserializing with Json.Net
  23. Get current method name from async function?
  24. WaitAll for multiple handles on a STA thread is not supported
  25. Resource from assembly as a stream
  26. Use coroutine inside a non MonoBehaviour class
  27. How do I get a return value from Task.WaitAll() in a console app?
  28. Throwing exceptions in callback method for Timers
  29. How does one “disable” a button in WPF using the MVVM pattern?
  30. Prevent timezone conversion on deserialization of DateTime value

Leave a Comment