7
\$\begingroup\$

I'm a beginner at C#. I just want to know what is the C# way to do this by its convention and a better algorithm as well.

using System;
using System.Collections.Generic;

public class Program
{
    static public void Main()
    {
        bool prime = false;
        List<int> non_primes = new List<int>();

        while (prime == false)
        {
            int number = 0;

            Console.Write("#: ");
            number = Convert.ToInt32(Console.ReadLine());

            prime = true;
            for (int i = 2; i <= number / 2; i++)
            {
                if (number % i == 0)
                    prime = false;

                if (prime == false)
                    non_primes.Add(number);
            }
        }

        if (non_primes.Count != 0)
            Console.WriteLine("none-primes: {0}", string.Join(" ", non_primes.ToArray()));
        else
            Console.WriteLine("none-primes: zero");

        Console.WriteLine("press any key to continue");
        Console.ReadKey();
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Here is some interesting way to do the same \$\endgroup\$
    – Firoz
    Apr 12 '16 at 11:03
  • \$\begingroup\$ Apart from anything else, use Int32.TryParse instead of Convert.ToInt32. Check this \$\endgroup\$ Apr 17 '16 at 21:26
4
\$\begingroup\$

I am no C# programmer, so I can't tell you much about the "C# way" to code. But I'll try to help you with your algorithm.

First things first, if I'm not mistaken your for-loop may fill the list of non-primes multiple times for a given number if it has more than one divisor. I'd suggest using the break; statement to exit the loop after you found the first, i.e.

for (int i = 2; i <= number / 2; i++)
        {
            if (number % i == 0){
                prime = false;
            }
            if (prime == false){
                nones.Add(number);
                break;
            }
        }

This will also save time by skipping unnecessary iterations. You should also increment by two instead of one, because all even numbers - and their multiples - will be divisible by two.

Since all numbers are either primes or multiples of primes you could further reduce compute time by skipping over numbers that are not prime. For example, fill an array with prime numbers below 100, then first try to divide the input by numbers in the array.
If it can't be divided by any of them, go back to the for-loop you already wrote and start from the highest prime you used.

\$\endgroup\$
1
  • \$\begingroup\$ For a suggestion on the primality-check; you have left out the most important: iterate to root(number) instead of number/2. Example: for 100 you only need to check up to multiples of 10 (10*10=100) , instead of check until 50 (2*50 =100). \$\endgroup\$
    – Ernst
    May 14 '16 at 20:13
4
\$\begingroup\$

... and a better algorithm as well.

I will address the "big picture" algorithm of this program, not the prime number bit.

Ideally, have the upper most method(s) read like a summary. This structured programming approach may seem like overkill for such a small program but even the smallest programs benefit from good structure.


using System;
using System.Collections.Generic;

public class Program
{
    static public void Main()
    {
        bool prime = false;
        List<int> non_primes = new List<int>();
        int number = 0;  // declare only one time. Not every time in a while loop.

        while (prime == false)
        {
           number = PromptForNumber();

            if(!IsPrime(number)){
                non_primes.Add(number);
            }else{
                prime = true;
            }
        }

        PrintNonPrimes(non_primes);
    }

    protected bool IsPrime (int candidatePrime) {
            bool isPrime = true;

            for (int i = 2; i <= candidatePrime / 2; i++)
            {
                if (candidatePrime % i == 0)
                    isPrime = false;
            }

            return isPrime;
    }

    protected int PromptForNumber() {
        Console.Write("#: ");
        return Convert.ToInt32(Console.ReadLine());
        // Put Convert in a try/catch block.
    }

    protected void PrintNonPrimes(List<int> nonPrimeCollection) {
        Console.WriteLine("Non Prime Numbers:");

        if(nonPrimeCollection.Count > 0) {
            foreach (var number in nonPrimeCollection) 
               Console.WriteLine(number);
        }else{
            Console.WriteLine("None");  
            // "zero" is a number spelled out. That might be confusing.
        }

        Console.WriteLine("press any key to continue");
        Console.ReadKey();
     }
}

  1. Main communicates overall function much better.
  2. Main is understood in 1/10th the time as the original.
  3. Each method, including Main, is focused on one thing.
    • Main is only "driving" the main steps of the program. It is not doing them.
  4. Focused methods are easier to read, understand, and change
  5. Changing focused methods tend to have no side effects - other methods don't have to change.
  6. Add checking for non-numbers in PrompForNumber and Main does not change at all.
  7. Completely rewrite the prime number algorithm in IsPrime and Main does not change at all.
  8. Modify any of the methods and the control logic in Main does not change.
  9. Coding errors are fewer. Debugging is easier.
\$\endgroup\$
1
  • \$\begingroup\$ radarbob your solution has some errors. You are referencing non static methods in static methods \$\endgroup\$
    – Tolani
    May 11 '16 at 9:02
4
\$\begingroup\$

Many good answers are already present but I would like to point out that enumerables are appropriate for this kind of problem, Main is just:

StreamOfInputNumbers()
  .TakeWhile(x => ! isPrime(x))
  .ToList()
  .ForEach(Console.WriteLine);

This reads like

Given a StreamOfInputNumbers, take items from it while (as long as) the number is not prime, (stop at the first prime), convert the numbers obtained so far (that are all not primes) to a list and print each one of them."

The main benefits of my suggestion are readability (as stated above), abstraction (reuse of the enumerator concept), conciseness (each concept like taking input or output is present only once) and separation of concerns (you could take the input numbers from a file or the web or generate them randomly just by changing the definition of StreamOfInputNumbers).

For completeness, here I include the definition of StreamOfInputNumbers:

static IEnumerable<int> StreamOfInputNumbers() {
  while (true) {
    yield return Int32.Parse(Console.ReadLine());
  }
}

(Note: The output format of this program is different from the output format of the code in the question, the new output format was chosen for simplicity as it seemed that the exact words were not a requirement. Adapting this code to different output formats should be easy.)

\$\endgroup\$
3
\$\begingroup\$

I looked at this piece of code that you have in your Main method

bool prime = false;
List<int> non_primes = new List<int>();

while (prime == false)
{
    int number = 0;

    Console.Write("#: ");
    number = Convert.ToInt32(Console.ReadLine());

    prime = true;
    for (int i = 2; i <= number / 2; i++)
    {
        if (number % i == 0)
            prime = false;

        if (prime == false)
            non_primes.Add(number);
    }
}

one thing that you should remember here is that a boolean variable doesn't need to be compared to a truthy value to get a truthy value out of it, so you could change the while conditional statement to "not prime" using the not operator (!) like this

while (!prime)

the next thing that I saw, was that you were converting the input to an integer, which is a good way to catch non integer input, the problem is that you will get an exception anytime the user enters something other than a number, I won't go into this much deeper than I already have, but you should look into int.TryParse you will find plenty of information on it if you do a Google Search for "int tryparse c#"

For now we will assume integer input.


I used a break statement to exit the for loop, I also merged the two if statements together because we already know prime is false because we set it to false. We want to stop going through the for loop as soon as we know the number is not prime otherwise we will add the same number to the non_primes list multiple times, and that is annoying.

this is what I came up with

bool prime = false;
List<int> non_primes = new List<int>();

while (prime == false)
{
    int number = 0;

    Console.Write("#: ");
    number = Convert.ToInt32(Console.ReadLine());

    prime = true;
    for (int i = 2; i <= number / 2; i++)
    {
        if (number % i == 0)
        {
            prime = false;
            non_primes.Add(number);
            break;
        }
    }
}

The break statement terminates the closest enclosing loop or switch statement in which it appears. Control is passed to the statement that follows the terminated statement, if any.

break (C# Reference)


you don't have any checks on the user's input, this could cause some weird things to happen during runtime.


Another thing that you could do is to skip numbers that you know are multiples of other numbers, like even numbers, this is the start of the Sieve of Eratosthenes, but it would cut your loop in half. we already know that 2 is a prime number and that 1 is a special case so you should have a special case for them, it will turn the run time into O(1) for those special cases.

So start at 3 and increment by 2 in the loop.

if (number == 1 || number == 2) {
    prime = true;
    break;
}
for (int i = 3; i <= number / 2; i += 2)
{
    if (number % i == 0)
    {
        prime = false;
        non_primes.Add(number);
        break;
    }
}

This is a good start to the Sieve of Eratosthenes you should go check it out.

\$\endgroup\$
2
  • \$\begingroup\$ We xan skip for number having end digit 0 too \$\endgroup\$ May 13 '16 at 12:44
  • 1
    \$\begingroup\$ if you skip even numbers then you skip numbers ending in 0 \$\endgroup\$
    – Malachi
    May 13 '16 at 12:47
1
\$\begingroup\$

With your current set up You should definitely break here :

    if (prime == false)
    {
        non_primes.Add(number);
        break;
    }

else if you enter big number it will print it many times.

This should rather be replaced with a short function determining if a number is a prime and breaking out of the loop if there's such occurrence :

    bool prime = false;
    List<int> non_primes = new List<int>();

    while (prime == false)
    {
        int number = 0;

        Console.Write("#: ");
        number = Convert.ToInt32(Console.ReadLine());

        prime = true;
        for (int i = 2; i <= number / 2; i++)
        {
            if (number % i == 0)
                prime = false;

            if (prime == false)
                non_primes.Add(number);
        }
    }

If you are sure you are taking string as input you should you use Int.Parse(x) instead of Convert.ToInt32(x) which takes object as input. Next as I said we are going to use function call here which will determine if a prime was found so your bool prime will become redundant. Next we need to create our bool function :

    private static bool IsPrime(int input)
    {
        for (int i = 2; i <= Math.Sqrt(input); i++)
        {
            if (input % i == 0)
            {
                return false;
            }
        }
        return true;
    }

Math.Sqrt(input) is much better than input/2. Now we need to create our while loop and break whenever we got prime number :

        List<int> non_primes = new List<int>();

        Console.Write("#: ");
        int number = int.Parse(Console.ReadLine());
        while (!IsPrime(number))
        {
            non_primes.Add(number);
            Console.Write("#: ");
            number = int.Parse(Console.ReadLine());
        }

The rest is the unchanged.

Exercice : You can try verifying your input using int.TryParse(),try/catch block, etc.

\$\endgroup\$
0
\$\begingroup\$

On the side algorithmic side of checking for primes in C#.

Yes, there are improvements!

  1. Your input is now limited to int32 ( 2,147,483,648 ), while you could have easily gone for Convert.ToInt64(input) or long.TryParse(number). This will accept input up to 9,223,372,036,854,775,808).
  2. i <= number / 2 , you don't need to check all the way up halve the number. For example if the input is 99, then the maximum multiple to check is 10 (10*10 = 100), anything else will be done by the inverse (2*50 = 50*2). so it should be i <= (long)System.Math.Sqrt(number)
  3. You might have unexpected behavior on 0 and negative numbers. Which are allowed due to conversion to int (signed) and not uint (unsigned)
  4. Read on what a prime is on wikipedia link1 and link2 and discover that if you rule out multiples of 2 and 3, every prime is the form 6n+1 or 6n-1

Like the others, make the prime-check functionality a separate method. It could look like this:

public static bool IsPrime(long candidate)
{
    // rule out 2 and 3
    if (candidate == 2 || candidate == 3) { return true; }
    // rule out multiples of 2 and 3; also 0/negative check
    if (candidate % 2 == 0 || candidate % 3 == 0 || candidate < 4) { return false; }
    long maxFactor = (long)System.Math.Sqrt(candidate);
    for (int p = 5; p <= maxFactor; p += 6)
    {   // all primes are 6n+1 or 6n-1 , see wikipedia; Only applies if 2 and 3 are already ruled out
        if (candidate % p == 0 || candidate % (p + 2) == 0)
        {   // number is divisible, thus not prime
            return false;
        }
    }
    return true; // not divisible, thus prime
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.