Формула простого числа

Question

Я пытаюсь написать функцию простого числа в C #, и мне интересно, будет ли работать следующий код.Похоже, что он работает с первыми 50 числами или около того.Я просто хочу убедиться, что он будет работать независимо от того, насколько велико число:

static bool IsPrime(int number)
{
    if ((number == 2) || (number == 3) || (number == 5) || (number == 7) || (number == 9))
            return true;

    if ((number % 2 != 0) && (number % 3 != 0) && (number % 5 != 0) &&
        (number % 7 != 0) && (number % 9 != 0) && (number % 4 != 0) &&
        (number % 6 != 0))
        return true;

        return false;
 }

Answer 1

Нет, это не сработает! Попробуйте, например, 121 = 11 * 11, который явно не простое число.

Для любого числа, данного вашей функции, которое является произведением простых чисел X1, X2, ..., Xn (где n> = 2 ), причем все они больше или равны 11, ваша функция вернет правда. (А также, как уже говорилось, 9 не простое число).

Из википедии вы можете видеть, что:

В математике простое число (или простое число) - это натуральное число, которое имеет ровно два различных делителя натуральных чисел: 1 и себя.

поэтому очень простой и наивный алгоритм проверки, является ли число простым, может быть:

public bool CalcIsPrime(int number) {

    if (number == 1) return false;
    if (number == 2) return true;

    if (number % 2 == 0) return false; // Even number     

    for (int i = 2; i < number; i++) { // Advance from two to include correct calculation for '4'
       if (number % i == 0) return false;
    }

    return true;

}

Для лучших алгоритмов проверьте здесь: Проверка на примитивность

Если вы хотите проверить свой код, выполните test , вот тестовый пример, написанный в xunit .

        [Theory]
        [MemberData(nameof(PrimeNumberTestData))]
        public void CalcIsPrimeTest(int number, bool expected) {
            Assert.Equal(expected, CalcIsPrime(number));
        }

        public static IEnumerable<object[]> PrimeNumberTestData() {
            yield return new object[] { 0, false };
            yield return new object[] { 1, false };
            yield return new object[] { 2, true };
            yield return new object[] { 3, true };
            yield return new object[] { 4, false };
            yield return new object[] { 5, true };
            yield return new object[] { 6, false };
            yield return new object[] { 7, true };
            yield return new object[] { 8, false };
            yield return new object[] { 9, false };
            yield return new object[] { 10, false };
            yield return new object[] { 11, true };
            yield return new object[] { 23, true };
            yield return new object[] { 31, true };
            yield return new object[] { 571, true };
            yield return new object[] { 853, true };
            yield return new object[] { 854, false };
            yield return new object[] { 997, true };
            yield return new object[] { 999, false };
        }

Answer 2

Это должно было быть сделано ...

public static bool IsPrime(this int number)
{
    return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 2);
}

Answer 3

Этот подход определенно не будет работать, если только ваш оператор if явно не перечисляет все простые числа от 0 до sqrt (INT_MAX) (или эквивалент C #).

Для правильной проверки на простоту, в основном, вам нужнопопытаться разделить ваше число на каждое простое число меньше его квадратного корня.Алгоритм Сито Эратосфена - ваш лучший выбор.

Answer 4

Вы, очевидно, пишете из контрафактного измерения, где 9 - простое число, поэтому я думаю, что наши ответы могут не сработать для вас.Хотя две вещи:

1. Функции генерации простых чисел - нетривиальный, но интересный вопрос, страница Википедии - хороший стартер (http://en.wikipedia.org/wiki/Formula_for_primes)

2. от(число% 2! = 0) следует (число% 4! = 0). Если вы не можете разделить на 10, то вы также не можете разделить на 100.

Answer 5

Это простой код для поиска простого числа в зависимости от вашего ввода.

  static void Main(string[] args)
    {
        String input = Console.ReadLine();
        long num = Convert.ToInt32(input);
        long a, b, c;
        c = 2;
        for(long i=3; i<=num; i++){
            b = 0;
            for (long j = 2; j < i ; j++) {
                a = i % j;
                if (a != 0) {
                    b = b+1;
                }
                else {
                    break;
                }
            }

            if(b == i-2){
                Console.WriteLine("{0}",i);
            }
        }
        Console.ReadLine();
    }

Answer 6

    static List<long> PrimeNumbers = new List<long>();

    static void Main(string[] args)
    {
        PrimeNumbers.Add(2);
        PrimeNumbers.Add(3);
        PrimeNumbers.Add(5);
        PrimeNumbers.Add(7);
        for (long i = 11; i < 10000000; i += 2)
        {
            if (i % 5 != 0)
                if (IsPrime(i))
                    PrimeNumbers.Add(i);
        }
    }

    static bool IsPrime(long number)
    {
        foreach (long i in PrimeNumbers)
        {
            if (i <= Math.Sqrt(number))
            {
                if (number % i == 0)
                    return false;
            }
            else
                break;
        }
        return true;
    }

Answer 7

это простое

только нечетные числа простые .... так что

static bool IsPrime(int number)
{
int i;
if(number==2)
    return true;                    //if number is 2 then it will return prime
for(i=3,i<number/2;i=i+2)           //i<number/2 since a number cannot be 
  {                                     //divided by more then its half
    if(number%i==0)                 //if number is divisible by i, then its not a prime
          return false;
  }
return true;                        //the code will only reach here if control
}                                       //is not returned false in the for loop

Answer 8

Есть несколько основных правил, которым вы можете следовать, чтобы проверить, простое ли число

1. Четные числа отсутствуют. Если x% 2 = 0, то оно не простое
2. Все не простые числа имеют простые множители. Таким образом, вам нужно только проверить число против простых чисел, чтобы увидеть, если оно учитывает
3. Максимально возможный коэффициент, который имеет любое число, - это квадратный корень. Вам нужно только проверить, можно ли делить значения <= sqrt (number_to_check). </li>

Используя этот набор логики, следующая формула вычисляет 1 000 000 простых чисел, сгенерированных за: 134,4164416 секунд в C # в одном потоке.

    public IEnumerable<long> GetPrimes(int numberPrimes)
    {
      List<long> primes = new List<long> { 1, 2, 3 };
      long startTest = 3;

      while (primes.Count() < numberPrimes)
      {
        startTest += 2;
        bool prime = true;
        for (int pos = 2; pos < primes.Count() && primes[pos] <= Math.Sqrt(startTest); pos++)
        {
          if (startTest % primes[pos] == 0)
          {
            prime = false;
          }
        }
        if (prime)
          primes.Add(startTest);
      }
      return primes;
    }

Имейте в виду, что в алгоритме достаточно места для оптимизации. Например, алгоритм может быть распараллелен. Если у вас есть простое число (скажем, 51), вы можете проверить все числа вплоть до его квадрата (2601) на предмет простоты в отдельных потоках, поскольку все возможные простые множители хранятся в списке.

Answer 9

Тестирование на примитивность - это путь, но если вам нужен быстрый и грязный хак, вот что.

Если это не работает достаточно быстро, вы можете построить класс вокруг него и сохранить коллекцию PrimeNumbers.от звонка к звонку, вместо того, чтобы заново заполнять его для каждого звонка.

    public bool IsPrime(int val)
    {
        Collection<int> PrimeNumbers = new Collection<int>();
        int CheckNumber = 5;
        bool divisible = true;
        PrimeNumbers.Add(2);
        PrimeNumbers.Add(3);

        // Populating the Prime Number Collection
        while (CheckNumber < val)
        {
            foreach (int i in PrimeNumbers)
            {
                if (CheckNumber % i == 0)
                {
                    divisible = false;
                    break;
                }
                if (i * i > CheckNumber) { break; }
            }
            if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
            else { divisible = true; }
            CheckNumber += 2;
        }
        foreach (int i in PrimeNumbers)
        {
            if (CheckNumber % i == 0)
            {
                divisible = false;
                break;
            }
            if (i * i > CheckNumber) { break; }
        }
        if (divisible == true) { PrimeNumbers.Add(CheckNumber); }
        else { divisible = true; }

        // Use the Prime Number Collection to determine if val is prime
        foreach (int i in PrimeNumbers)
        {
            if (val % i == 0) { return false; }
            if (i * i > val) { return true; }
        }
        // Shouldn't ever get here, but needed to build properly.
        return true;
    }

Answer 10

Здесь мы должны учитывать фактор квадратного корня. Простое число можно проверить, если оно не делится на любое число, меньшее значения квадратного корня любого близкого числа.

static bool isPrime(long number) 
{
    if (number == 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false; //Even number     
    long nn= (long) Math.Abs(Math.Sqrt(number));
    for (long i = 3; i < nn; i += 2)  {
       if (number % i == 0) return false;
    }
    return true;
}