C - определить, является ли число простым - PullRequest
Новая
       32

C - определить, является ли число простым

70 голосов
/ 08 октября 2009

Я пытаюсь найти метод, который принимает целое число и возвращает логическое значение, чтобы сказать, является ли число простым или нет, и я не знаю много C; кто-нибудь захочет дать мне несколько советов?

В принципе, я бы сделал это на C # так: 

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

Ответы [ 11 ]

0 голосов
/ 12 мая 2016

Используя сито Эратосфена, вычисления выполняются намного быстрее по сравнению с «общеизвестным» алгоритмом простых чисел.

Используя псевдокод из вики (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes),, я смогу найти решение на C #. 

public bool IsPrimeNumber(int val) {
    // Using Sieve of Eratosthenes.
    if (val < 2)
    {
        return false;
    }

    // Reserve place for val + 1 and set with true.
    var mark = new bool[val + 1];
    for(var i = 2; i <= val; i++)
    {
        mark[i] = true;
    }

    // Iterate from 2 ... sqrt(val).
    for (var i = 2; i <= Math.Sqrt(val); i++)
    {
        if (mark[i])
        {
            // Cross out every i-th number in the places after i (all the multiples of i).
            for (var j = (i * i); j <= val; j += i)
            {
                mark[j] = false;
            }
        }
    }

    return mark[val];
}

IsPrimeNumber (1000000000) занимает 21 с 758 мс.

ПРИМЕЧАНИЕ : значение может отличаться в зависимости от технических характеристик оборудования.

Страница:
...