Optimizing the search for prime numbers

Question

I created a function for finding Prime Numbers, but the process takes a long time and uses a lot of memory. I need to optimize my code by making it more time and memory efficient.

The function is split into two parts:

The 1st part calculates odd numbers, the 2nd part is the isSimple method which searches for odd numbers that are prime.

I made some progress by moving the Math.Sqrt(N) outside of the for loop, but I'm not sure what to do next.

Any suggestions are welcome.

Program:

class Program
{
    static void Main(string[] args)
    {
        //consider odd numbers
        for (int i = 10001; i <=90000; i+=2)
        {
            if (isSimple(i))
            {
                 Console.Write(i.ToString() + "\n");
            }
        }
    }
  //The method of finding primes
    private static bool isSimple(int N)
    {
        double koren = Math.Sqrt(N);

         // to verify a prime number or not enough to check whether it is //divisible number on numbers before its root
        for (int i = 2; i <= koren; i++)
        {   
            if (N % i == 0)
                 return false;
        }
        return true;
    }
}

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. You've merely dumped a homework problem on us. We have no idea what *your* problem is. — Prune, Mar 22 '18 at 17:38
This approach does not eat memory. If you want to trade speed for memory, consider Eratosthenes sieve — MBo, Mar 22 '18 at 17:40
I need advice on how to change the code, for me, speed, and fun consumed memory — user9534998, Mar 22 '18 at 17:40
see [Prime numbers by Eratosthenes quicker sequential than concurrently?](https://stackoverflow.com/a/22477240/2521214) — Spektre, Mar 22 '18 at 17:41
@Jack Where did you get that I did not optimize these functions? — user9534998, Mar 22 '18 at 17:46
@Jack Did not find it necessary. Do you need to know what I corrected before to find flaws in this code? — user9534998, Mar 22 '18 at 17:52
If you want help on optimizing your code, it would be good to see some methods you have tried so far. Make your question sound like a discussion, not a task. — Jack, Mar 22 '18 at 17:55
@Jack Thanks, understood. Earlier introduced instead of dividing the root. And inserted it before the cycle — user9534998, Mar 22 '18 at 18:06

score 0 · Answer 1 · answered Mar 23 '18 at 09:05

You are checking all possible divisors with your for (int i = 2; i <= koren; i++) That wastes time. You can halve the time taken by checking only odd divisors. You know that the given number N is odd, so no even number can be a divisor. Try for (int i = 3; i <= koren; i+=2) instead.

Optimizing the search for prime numbers

1 Answers1