Program to find prime numbers

Question

I want to find the prime number between 0 and a long variable but I am not able to get any output.

The program is

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();
        }
    }
}

Can any one help me out and find what is the possible error in the program?

Answer 1

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 2

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 3

ExchangeCore Forums have a good console application listed that looks to write found primes to a file, it looks like you can also use that same file as a starting point so you don't have to restart finding primes from 2 and they provide a download of that file with all found primes up to 100 million so it would be a good start.

The algorithm on the page also takes a couple shortcuts (odd numbers and only checks up to the square root) which makes it extremely efficient and it will allow you to calculate long numbers.

Answer 4

People have mentioned a couple of the building blocks toward doing this efficiently, but nobody's really put the pieces together. The sieve of Eratosthenes is a good start, but with it you'll run out of memory long before you reach the limit you've set. That doesn't mean it's useless though -- when you're doing your loop, what you really care about are prime divisors. As such, you can start by using the sieve to create a base of prime divisors, then use those in the loop to test numbers for primacy.

When you write the loop, however, you really do NOT want to us sqrt(i) in the loop condition as a couple of answers have suggested. You and I know that the sqrt is a "pure" function that always gives the same answer if given the same input parameter. Unfortunately, the compiler does NOT know that, so if use something like '<=Math.sqrt(x)' in the loop condition, it'll re-compute the sqrt of the number every iteration of the loop.

You can avoid that a couple of different ways. You can either pre-compute the sqrt before the loop, and use the pre-computed value in the loop condition, or you can work in the other direction, and change i<Math.sqrt(x) to i*i<x. Personally, I'd pre-compute the square root though -- I think it's clearer and probably a bit faster--but that depends on the number of iterations of the loop (the i*i means it's still doing a multiplication in the loop). With only a few iterations, i*i will typically be faster. With enough iterations, the loss from i*i every iteration outweighs the time for executing sqrt once outside the loop.

That's probably adequate for the size of numbers you're dealing with -- a 15 digit limit means the square root is 7 or 8 digits, which fits in a pretty reasonable amount of memory. On the other hand, if you want to deal with numbers in this range a lot, you might want to look at some of the more sophisticated prime-checking algorithms, such as Pollard's or Brent's algorithms. These are more complex (to put it mildly) but a lot faster for large numbers.

There are other algorithms for even bigger numbers (quadratic sieve, general number field sieve) but we won't get into them for the moment -- they're a lot more complex, and really only useful for dealing with really big numbers (the GNFS starts to be useful in the 100+ digit range).

Answer 5

U can use the normal prime number concept must only two factors (one and itself). So do like this,easy way

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
    class Program
    {
        static void FindPrimeNumber(long num)
        {
            for (long i = 1; i <= num; i++)
            {
                int totalFactors = 0;
                for (int j = 1; j <= i; j++)
                {
                    if (i % j == 0)
                    {
                        totalFactors = totalFactors + 1;
                    }
                }
                if (totalFactors == 2)
                {
                    Console.WriteLine(i);
                }
            }
        }

        static void Main(string[] args)
        {
            long num;
            Console.WriteLine("Enter any value");
            num = Convert.ToInt64(Console.ReadLine());
            FindPrimeNumber(num);
            Console.ReadLine();
        }
    }
}

Answer 6

I know this is quiet old question, but after reading here: Sieve of Eratosthenes Wiki

This is the way i wrote it from understanding the algorithm:

void SieveOfEratosthenes(int n)
{
    bool[] primes = new bool[n + 1];

    for (int i = 0; i < n; i++)
        primes[i] = true;

    for (int i = 2; i * i <= n; i++)
        if (primes[i])
            for (int j = i * 2; j <= n; j += i)
                primes[j] = false;

    for (int i = 2; i <= n; i++)
        if (primes[i]) Console.Write(i + " ");
}

In the first loop we fill the array of booleans with true.

Second for loop will start from 2 since 1 is not a prime number and will check if prime number is still not changed and then assign false to the index of j.

last loop we just printing when it is prime.