Checking for a prime number

Question

I'm having problems with a task. I need to find and alert the user if the number is prime or not.

Here is my code:

int a = Convert.ToInt32(number);

if (a % 2 !=0 )
{
    for (int i = 2; i <= a; i++)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
        }
        else
        {
            Console.WriteLine("prime");
        }
        Console.WriteLine();
    }
}
else
{
    Console.WriteLine("not prime");
}
Console.ReadLine();

Where did I go wrong, and how can I fix it?

Answer 1

    private static void checkpirme(int x)
    {
        for (int i = 1; i <= x; i++)
        {
            if (i == 1 || x == i)
            {
                continue;
            }
            else
            {
                if (x % i == 0)
                {
                    Console.WriteLine(x + " is not prime number");
                    return;
                }


            }
        }
        Console.WriteLine(x + " is  prime number");
    }

where x is number to check it if prime or not

Answer 2

Yet another optimized way is to use Sieve of Eratosthenes algorithm.

From Wikipedia

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These will be multiples of p: 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

C# code

  int[] GetPrimes(int number) // input should be greater than 1
    {
        bool[] arr = new bool[number + 1];
        var listPrimes = new List<int>();

        for (int i = 2; i <= Math.Sqrt(number); i++)
        {
            if (!arr[i])
            {
                int squareI = i * i;
                for (int j = squareI; j <= number; j = j + i)
                {
                    arr[j] = true;
                }
            }

            for (int c = 1; c < number + 1; c++)
            {
                if (arr[c] == false)
                {
                    listPrimes.Add(c);
                }
            }

        }
        return listPrimes.ToArray();
    }

Answer 3

I've done far too much prime checking.

I did this:

bool isPrime = true;
        List<ulong> primes = new List<ulong>();
        ulong nCheck, nCounted;
        nCounted = 0;
        nCheck = 3;
        primes.Add(2);
        for (; ; )
        {
            isPrime = true;
            foreach (ulong nModulo in primes)
            {
                if (((nCheck / 2) + 1) <= nModulo)
                { break; }
                if (nCheck % nModulo == 0)
                { isPrime = false; }
            }
            if (isPrime == true)
            {
                Console.WriteLine("New prime found: " + (nCheck) + ", prime number " + (++nCounted) + ".");
                primes.Add(nCheck);
            }
            nCheck++;
            nCheck++;
        }

This is not EXACTLY what you are looking for though, so what I'd do is put this in a background worker, but with the list of ulongs as a concurrent list, or something that you can access in 2 threads. Or just lock the list while it's being accessed. If the prime hssn't been worked out yet, wait until it is.

Answer 4

Presumably your code is outputting lots of messages, which seem jumbled and meaningless? There are 3 key issues:

• You arn't breaking out of your for loop when you've decided it can't be prime

• You are assuming it is prime when it might not be, see the comments in the code below.

• You are comparing to a itself, and that will always be divisible by a, the <= in the for condition needs to be <

Code:

int a = Convert.ToInt32(number);

if (a % 2 != 0)
{
    for (int i = 3 i < a; i += 2) // we can skip all the even numbers (minor optimization)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
            goto escape; // we want to break out of this loop
        }
        // we know it isn't divisible by i or any primes smaller than i, but that doesn't mean it isn't divisible by something else bigger than i, so keep looping 
    }
    // checked ALL numbers, must be Prime
    Console.WriteLine("prime");
}
else
{
    Console.WriteLine("not prime");
}
escape:
Console.ReadLine();

As other have mentioned, you could only loop to the square root of the a, by per-evaluating the square root and replacing this line:

for (int i = 3 i < a; i += 2)

with this:

float sqrRoot = (Int)Math.Sqrt((float)a);
for (int i = 3 i <= sqrRoot; i += 2)

It is important to per-evaluate it else your program will run much slower, rather than faster, as each iteration will involve a square root operation.

If you don't like goto statements (I love goto statements), post a comment and I'll replace it will a breakout boolean (or see Dukeling's more recent answer).

Answer 5

Prime numbers is divisible by 1 and themselves you will need to check if number has exactly two divisor starting from one till number then it is prime.

 int devisors = 0;
 for (int i = 1; i <= a; i++)
     if (a % i == 0)                        
          devisors++;

 if (devisors == 2)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

You can skip one iteration as we know all whole numbers are divisible by 1 then you will have exactly on divisor for prime numbers. Since 1 has only one divisor we need to skip it as it is not prime. So condition would be numbers having only one divisor other then 1 and number should not be one as one is not prime number.

 int devisors = 0;
 for (int i = 2; i <= a; i++)
     if (a % i == 0)                        
          devisors++;

 if (a != 1 && devisors == 1)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

Answer 6

You just printed prime or not prime, and continued with the loop, rather than stopping. The %2 check is not really needed. Modified appropriately:

int a = Convert.ToInt32(number);

bool prime = true;
if (i == 1) prime = false;
for (int i = 2; prime && i < a; i++)
    if (a % i == 0) prime = false;
if (prime) Console.WriteLine("prime");
else Console.WriteLine("not prime");
Console.ReadLine();

Answer 7

public bool isPrime(int num)
{
    for (int i = 2; i < num; i++)
        if (num % i == 0) 
            return false;                       
    return num == 1 ? false : true;
}