sandy101 - 1 year ago 67

C# 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 Source

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).