Program to find prime numbers

Question

I'm trying to construct a program that finds prime numbers between zero and the number input (a really long number); but the program isn't returning an output like I'm expecting it to:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication16
{
    class Program
    {


        void prime_num(long num)
        {

            bool isPrime = true;
            for (int i = 0; i <= num; i++)
            {
                for (int j = 2; j <= num; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                Console .WriteLine ( "Prime:" + i );
                }
                isPrime = true;
            }
        }



        static void Main(string[] args)
        {
            Program p = new Program();
            p.prime_num (999999999999999L);
            Console.ReadLine();

        }
    }
}

What errors do you see in this program? How can I make it better?

Answer 1

Smells like more homework. My very very old graphing calculator had a is prime program like this. Technnically the inner devision checking loop only needs to run to i^(1/2). Do you need to find "all" prime numbers between 0 and L ? The other major problem is that your loop variables are "int" while your input data is "long", this will be causing an overflow making your loops fail to execute even once. Fix the loop variables.

Answer 2

Try removing the "break", it seems to me that it takes you out of the inner for loop prematurely.

Answer 3

You can do this faster using a Sieve of Eratosthenes in one (long) line like this:

Enumerable.Range(0, num).Aggregate(
    Enumerable.Range(2, 1000000).ToList(), 
    (result, index) => { 
        result.RemoveAll(i => i > result[index] && i % result[index] == 0); 
        return result; 
    }
);

Answer 4

Try this:

void prime_num(long num)
{

    // bool isPrime = true;
    for (long i = 0; i <= num; i+=2)
    {
        bool isPrime = true; // Move initialization to here
        for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
        {
            if (i % j == 0) // you don't need the first condition
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            Console.WriteLine ( "Prime:" + i );
        }
        // isPrime = true;
    }
}

Answer 5

You only need to check odd divisors up to the square root of the number. In other words your inner loop needs to start:

for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }

You can also break out of the function as soon as you find the number is not prime, you don't need to check any more divisors (I see you're already doing that!).

This will only work if num is bigger than two.

No Sqrt

You can avoid the Sqrt altogether by keeping a running sum. For example:

int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}

This is because the sum of numbers 1+(3+5)+(7+9) will give you a sequence of odd squares (1,9,25 etc). And hence j represents the square root of square_sum. As long as square_sum is less than i then j is less than the square root.

Answer 6

Very similar - from an exercise to implement Sieve of Eratosthenes in C#:

public class PrimeFinder
{
    readonly List<long> _primes = new List<long>();

    public PrimeFinder(long seed)
    {
        CalcPrimes(seed);
    }

    public List<long> Primes { get { return _primes; } }

    private void CalcPrimes(long maxValue)
    {
        for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
        {
            if (IsPrime(checkValue))
            {
                _primes.Add(checkValue);
            }
        }
    }

    private bool IsPrime(long checkValue)
    {
        bool isPrime = true;

        foreach (long prime in _primes)
        {
            if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
            {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
}

Answer 7

It may just be my opinion, but there's another serious error in your program (setting aside the given 'prime number' question, which has been thoroughly answered).

Like the rest of the responders, I'm assuming this is homework, which indicates you want to become a developer (presumably).

You need to learn to compartmentalize your code. It's not something you'll always need to do in a project, but it's good to know how to do it.

Your method prime_num(long num) could stand a better, more descriptive name. And if it is supposed to find all prime numbers less than a given number, it should return them as a list. This makes it easier to seperate your display and your functionality.

If it simply returned an IList containing prime numbers you could then display them in your main function (perhaps calling another outside function to pretty print them) or use them in further calculations down the line.

So my best recommendation to you is to do something like this:

public void main(string args[])
{
    //Get the number you want to use as input
    long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments

    IList<long> primes = FindSmallerPrimes(number);

    DisplayPrimes(primes);
}

public IList<long> FindSmallerPrimes(long largestNumber)
{
    List<long> returnList = new List<long>();
    //Find the primes, using a method as described by another answer, add them to returnList
    return returnList;
}

public void DisplayPrimes(IList<long> primes)
{
    foreach(long l in primes)
    {
        Console.WriteLine ( "Prime:" + l.ToString() );
    }
}

Even if you end up working somewhere where speration like this isn't needed, it's good to know how to do it.