Checking to see if the number the user entered is a prime number

Question

This particular question does not involve loops and most of the answers I have seen involve loops. This is a challenge from one of the books I am reading. No, I'm not a student (38 years old) I'm actually switching careers, so I've decided to start learning how to program. The book I am reading is called "Introduction to C# / Joes 2 Pros".

Here's the code I have so far. I know there is more than likely a better way to do this using things I probably don't have a good grasp on. For example, I know what a "bool" is, but just haven't used it in any of my coding yet. Therefore, it's difficult to implement it.

    int myChoice;
    Console.Write("Please enter a number: ");
    myChoice = int.Parse(Console.ReadLine());

    if (myChoice >= 1 && myChoice % myChoice == 0)
    {
        Console.WriteLine("That's correct, {0} is a prime number.", myChoice);
    }
    else
    {
        Console.WriteLine("That is not a prime number.");
    }

    Console.ReadLine();

OK, as you can see the program asks for the user to enter a number. As determined by the if statement, if the number is greater than or equal to 1 AND the number is divisible by itself with no remainder, the statement is true.

I know there is a much better way of finding out if the number entered is a prime, but I just can't figure out what it is. The program does what I expect it to do except figuring out if the number is prime.

Just a bit of background here. What you are seeing on the screen is just about the extent of my knowledge of C#. Beyond what you see, I'm probably lost.

Any suggestions?

Just FYI, *every* number (except zero) divides itself with no remainder. The definition of a prime is whether a number is only divisible by 1 and itself, meaning no *other* numbers divide it. — Brian Rogers, Jun 05 '13 at 02:10
http://stackoverflow.com/questions/15743192/check-if-number-is-prime-number — cuongle, Jun 05 '13 at 02:12
Your program prints any number as prime number. Search on google how to check if the number is prime. I suggest you to go through algorithms with pseudo code or in other language C and implement in C#. — Sunny, Jun 05 '13 at 02:12
Yes, my code is written wrong. That was kind of the point (which I failed to explain). Every number is divisible by itself and 1 which my code does explain. However, I was trying to find one more && statement that would check to see if it were a prime number. I'm not thinking about this correctly, obviously. — Chris Smith, Jun 05 '13 at 02:21
Just to add something here. I don't know any other languages. C# is my first. Some might say that's a bit odd, but I'm rather enjoying it. — Chris Smith, Jun 05 '13 at 02:23
The point is, you can't check for prime without some kind of loop (or recursion). Just "adding one more &&" doesn't do it. — Brian Rogers, Jun 05 '13 at 02:25
@Brian Rogers: Adding one more && was just a thought. It was something I had thought about doing, not that it was necessarily needed. If this requires a loop then I need to go back and study how I might pull this off. — Chris Smith, Jun 05 '13 at 02:29
@BrianRogers two words. [Wilson's Theorem.](http://en.wikipedia.org/wiki/Wilson%27s_theorem) — Aron, Jun 05 '13 at 03:05
@Aron But computing the factorial (`mod n`) would involve a loop or recursion. — Daniel Fischer, Jun 05 '13 at 10:20
@DanielFischer depends entirely on your algorithm...[Gamma Function](http://en.wikipedia.org/wiki/Gamma_function). — Aron, Jun 05 '13 at 10:25
@Aron Now, implementing a sufficiently accurate gamma function is hard enough. Doing it without loops or recursion? — Daniel Fischer, Jun 05 '13 at 10:41
@Aron the correct answer to Daniel's objection is: *"it's a library function, whadda I care!"* :) :) — Will Ness, Jun 06 '13 at 16:29

score 1 · Answer 1 · answered Jun 05 '13 at 02:09

1

There is another very challenging requirement to test for prime, it must not divide by any other numbers. For example 4 is greater than zero and 4 % 4 = 0. But 4 is not a prime, it is equal to 2x2.

Testing for prime is rather difficult. Most starting programming books want you to experiment with the Sieve of Eratosthenes, which is an old way to determine if a number is a prime. The wiki page proposes an algorithm to implement for this. Basically you generate numbers from 1 to 100 in an array and remove those who are not prime, leaving you all primes from 1 to 100.

answered Jun 05 '13 at 02:09

Eric

19,525
19
84
147

It's kind of funny that a beginners book would ask a beginner to write a program that checks to see if the user entered a prime number. Seems like a huge oversight by the editor or Author. – Chris Smith Jun 05 '13 at 02:22
1

To be faire, the complexity is not with the language, but with the algorithmic complexity involved. If it is a book that allows you to switch from say, C++ to C#, then yes this is appropriate. – Eric Jun 05 '13 at 02:27
1

Really, all you need to check for primality is 2 for loops and a boolean – Eric Jun 05 '13 at 02:28
@ChrisSmith number theory is seriously NOT an easy subject. Most efficient algorithms for testing "primeness" run several different algorithms. The fastest algorithms can only test for "probable primeness". The fastest deterministic prime tests require that Riemann's hypothesis be true. Generally commercial algorithms test primeness by first testing for probable primenesss followed by deterministic primeness. If anything I just described meant nothing to you...this is a fool's errant. – Aron Jun 05 '13 at 02:38

score 1 · Answer 2 · edited Jun 06 '13 at 16:36

If your number n is small, it is simple to test all numbers less than sqrt(n) as divisors; if none of them divide n, then n is prime:

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return Composite
        d := d + 1
    return Prime

For larger numbers, a reasonable test of primality is the Miller-Rabin test; it can be fooled (falsely proclaim that a composite number is prime) but with very low likelihood. Start with a strong pseudoprime test:

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d is even
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return DefinitelyComposite

Each a for which the function returns ProbablyPrime is a witness to the primality of n; test enough of them and you gain some confidence that n is actually prime:

function isPrime(n)
    for i from 1 to k
        a := randint(2 .. n-1)
        if isStrongPseudoprime(n, a) == DefinitelyComposite
            return DefinitelyComposite
    return ProbablyPrime

Variable k is the number of trials you want to perform; somewhere between 10 and 25 is typically a reasonable value. The powerMod(b,e,m) function returns b ^ e (mod m). If your language doesn't provide that function, you can efficiently calculate it like this:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

If you're interested in the math behind this test, I modestly recommend the essay Programming with Prime Numbers at my blog.

Checking to see if the number the user entered is a prime number

2 Answers2