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

You can do this faster using a nearly optimal trial division sieve in one (long) line like this:

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(     Enumerable.Range(2, num-1).ToList(),      (result, index) => {          var bp = result[index]; var sqr = bp * bp;         result.RemoveAll(i => i >= sqr && i % bp == 0);          return result;      } ); 

The approximation formula for number of primes used here is π(x) < 1.26 x / ln(x). We only need to test by primes not greater than x = sqrt(num).

Note that the sieve of Eratosthenes has much better run time complexity than trial division (should run much faster for bigger num values, when properly implemented).

Answer 2

Try this:

void prime_num(long num) {      // bool isPrime = true;     for (long i = 0; i <= num; i++)     {         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;     } }