функция для проверки, является ли число простым или нет?

Question

Мне нужен был способ проверить, является ли заданное число простым или нет. Я искал в Интернете, и я нашел разные функции, но они были сложными. Итак, я разработал свой собственный метод проверки того, является ли число простым или нет. Он работает для меня. Я просто хочу знать, правильно это или нет. Код приводится ниже:

bool IsPrime(int n) 
{ 
    for (int i = 2; i <= 7; i++) 
    { 
     if (i < n && n % i == 0) 
     { 
      return false; 
     } 
     if (i == n) 
     { 
      return true; 
     } 
    } 
    return true; 
} 

Answer 1

Короткий ответ: Нет, это неверно.

Kind Ответ: Вот рабочий код:

bool IsPrime(int n) 
{ 
    if (n <= 1) return false;  // .. , -1, 0, 1 
    if (n == 2) return true;  // 2 
    if (n % 2 == 0) return false; // 4, 6, 8, ... 
    int sqrt = (int)Math.Sqrt(n); // largest possible factor   
    for (int i = 3; i <= sqrt; i+=2) 
    { 
     if (n % i == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

Примечание: Есть много алгоритм, который работает лучше, быстрее и т.д. ...

---

Редактировать

Использование идеи @ Blastfurnace и еще несколько h с оптимизированным вариантом:

bool IsPrime(int n) 
{ 
    if (n <= 1) return false;  // .. , -1, 0, 1  
    if (n % 2 == 0) return (n==2); // 2 and even numbers 
    if (n % 3 == 0) return (n==3); // 3 and divisible by 3 
    if (n % 5 == 0) return (n==5); 
    if (n % 7 == 0) return (n==7); // the magic 7 from OP 
    if (n < 11) return false; 
    // calc sqrt as rare as possible, its expensive 
    int sqrt = (int)Math.Sqrt(n); // largest possible factor 
    // skip 9, already done with n%3 
    for (int i = 11; i <= sqrt; i+=2) if (n % i == 0) return false; 

    return true; 
} 

Это должно сэкономить несколько циклов процессора.

Answer 2

Из определения простого числа "Целое число больше единицы называется простым числом, если его единственные положительные делители (факторы) являются единичными и сами по себе.", 0 и 1 не являются простыми числами.

Коррекция ответа DrKoch в:

bool IsPrime(int n) 
{ 
    if(n == 0 || n == 1) 
     return false; 
    else if(n == 2) 
     return true; 
    else if(n%2 == 0) 
     return false; 
    else { 
     int sqrt = (int)Math.Sqrt(n); 

     for (int i = 3; i <= sqrt; i+=2) 
     { 
      if (n % i == 0) 
       return false; 
     } 

     return true; 
    } 
}