Самый элегантный способ генерировать простые числа [закрыто]

84

Как наиболее элегантно реализовать эту функцию:

ArrayList generatePrimes(int n)

Эта функция генерирует первые nпростые числа (edit: where n>1), поэтому generatePrimes(5)вернет ArrayListwith {2, 3, 5, 7, 11}. (Я делаю это на C #, но я доволен реализацией Java - или любым другим подобным языком в этом отношении (но не Haskell)).

Я знаю, как написать эту функцию, но когда я сделал это вчера вечером, все закончилось не так хорошо, как я надеялся. Вот что я придумал:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

Меня не слишком заботит скорость, хотя я не хочу, чтобы она была явно неэффективной. Меня не волнует, какой метод используется (наивный или сито или что-то еще), но я хочу, чтобы он был достаточно коротким и очевидным, как он работает.

Изменить : Спасибо всем, кто ответил, хотя многие не ответили на мой вопрос. Повторюсь, мне нужен хороший чистый фрагмент кода, который генерирует список простых чисел. Я уже знаю, как это сделать по-разному, но я склонен писать код, который не так понятен, как мог бы. В этой ветке было предложено несколько хороших вариантов:

  • Лучшая версия того, что у меня было изначально (Питер Смит, jmservera и Rekreativc)
  • Очень чистая реализация сита Эратосфена (звездно-синий)
  • Используйте Java BigIntegers и nextProbablePrimeдля очень простого кода, хотя я не могу представить, чтобы он был особенно эффективным (dfa)
  • Используйте LINQ для ленивого создания списка простых чисел (Maghis)
  • Поместите много простых чисел в текстовый файл и при необходимости прочтите их (дарин)

Изменить 2 : я реализовал на C # несколько методов, приведенных здесь, и еще один метод, не упомянутый здесь. Все они эффективно находят первые n простых чисел (и у меня есть приличный метод определения предела, который нужно предоставить решетам).

Дэвид Джонстон
источник
12
нет, и это тоже не для Project Euler :-)
Дэвид Джонстон
1
было бы лучше, чтобы я возвращал ienumerable <int> и уступал один за другим
Felice Pollano
4
Я хотел бы знать, какой способ генерирования простых чисел является наименее элегантным. Я что-то думаю о базе данных Access?
j_random_hacker
1
для сравнения, 2008 Haskell код по BMeph : nubBy (((>1).).gcd) [2..]. Он оставляет только неповторяющиеся среди натуральных чисел, начиная с 2, при этом рассматривая как дубликаты любое число, gcdлюбое из ранее найденных чисел больше 1. Это очень неэффективно, квадратично по количеству произведенных простых чисел. Но это элегантно .
Уилл Несс,
самый элегантный , IMO, принадлежит Haskell, import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) }но он, конечно, полностью основан на мнении .
Уилл Несс

Ответы:

48

Воспользуйтесь оценкой

pi(n) = n / log(n)

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

Это мое стандартное сито Java, вычисляет первый миллион простых чисел примерно за секунду на обычном ноутбуке:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}
звездно-голубой
источник
3
Это очень хорошая реализация сита Эратосфена
Дэвид Джонстон
1
Разве этого не достаточно, чтобы зациклить во i <= Math.sqrt(limit)внешнем цикле?
Christoph
1
@ Дэвид Джонстон: Нет, pi (n) = n / log (n) недооценивает количество простых чисел до n, которое идет в противоположном направлении. Однако я рад, что вы нашли более подходящее приближение.
starblue 04
1
если вы хотите удалить все числа, кратные 2, в собственном цикле, вы можете использовать j + = 2 * i в качестве приращения цикла, чтобы сэкономить дополнительное время выполнения, и вы можете вычислить это один раз, используя битовый сдвиг
Ник Ларсен,
5
При замене BitSetклассом, реализующим факторизацию колеса для 2, 3 и 5, он становится почти в 3 раза быстрее.
starblue
37

Большое спасибо всем, кто дал полезные ответы. Вот мои реализации нескольких различных методов поиска первых n простых чисел в C #. Первые два метода в значительной степени соответствуют тому, что было опубликовано здесь. (Имена плакатов указаны рядом с заголовком.) Я планирую когда-нибудь заняться ситом Аткина, хотя подозреваю, что это будет не так просто, как методы, которые здесь представлены сейчас. Если кто-нибудь может увидеть способ улучшить любой из этих методов, я хотел бы знать :-)

Стандартный метод ( Питер Смит , jmservera , Rekreativc )

Первое простое число - 2. Добавьте это в список простых чисел. Следующее простое число - это следующее число, которое не делится без остатка ни на какое число в этом списке.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

Это было оптимизировано только проверкой делимости до квадратного корня из проверяемого числа; и проверкой только нечетных чисел. Это может быть дополнительно оптимизирована путем тестирования только числа вида 6k+[1, 5], или , 30k+[1, 7, 11, 13, 17, 19, 23, 29]или так далее .

Сито Эратосфена ( звездно-голубое )

Это находит все простые числа k . Чтобы составить список из первых n простых чисел, нам сначала нужно приблизить значение n- го простого числа. Это делает следующий метод, описанный здесь .

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

Сито Сундарама

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

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}
Дэвид Джонстон
источник
FYI - мне пришлось изменить ваш основной счетчик цикла на «for (int i = 0; i * i <= limit && i * i> 0; i ++)», чтобы предотвратить переполнение.
Jacobs Data Solutions
Эта реализация Решета Сундарама - одна из очень немногих правильных. Большинство из них используют неправильные границы для i и j при вычислении, что i+j+2*i*jприводит к неправильному выводу.
jahackbeth
16

Повторяю старый вопрос, но я наткнулся на него, играя с LINQ.

Для этого кода требуется .NET4.0 или .NET3.5 с параллельными расширениями

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}
spookycoder
источник
1
Почему это не принятый ответ? Код здесь намного короче, элегантнее и быстрее, чем код в принятом ответе. Хотел бы я проголосовать больше одного раза!
Аврохом Исроэль
9

Вы на правильном пути.

Некоторые комментарии

  • простые числа.Добавить (3); делает, что эта функция не работает для number = 1

  • Вам не нужно проверять деление с простыми числами, большими, чем квадратный корень проверяемого числа.

Предлагаемый код:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}
Питер Смит
источник
1
тестирование этого prime * prime <= curTest в цикле вместо предварительного вычисления квадратного корня, вероятно, ускорит его и сделает его более универсальным (будет работать для bignums и т. д.)
yairchu
Зачем использовать квадратный корень? Какова математическая подоплека такого варианта? Я бы, наверное, тупо, разделил бы только на 2.
Луис Филипе
3
Потому что, если у числа есть простые множители, по крайней мере один из них должен быть меньше или равен квадратному корню. Если a * b = c и a <= b, тогда a <= sqrt (c) <= b.
Дэвид Джонстон
8

вам следует взглянуть на вероятные простые числа . В частности, обратите внимание на рандомизированные алгоритмы и тест простоты Миллера – Рабина .

Для полноты вы можете просто использовать java.math.BigInteger :

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}
DFA
источник
2
Miller-Rabbin работает очень быстро, а код очень прост. Достаточное количество итераций делает его достаточно надежным, чтобы конкурировать со случайным отказом ЦП с точки зрения вероятности ложного срабатывания. Обратной стороной алгоритма является то, что понять, почему он на самом деле работает, - сложная задача.
Брайан,
6

Отнюдь не эффективный, но, возможно, самый читаемый:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

с участием:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

Фактически, это просто вариант некоторых сообщений с более красивым форматированием.

RaphM
источник
5

Авторские права 2009 г. Сент-Виттум 13189 Берлин ГЕРМАНИЯ по лицензии CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

Самый простой, но самый элегантный способ вычисления ВСЕХ ПЕРВИЧНЫХ - это, но этот способ медленный, и затраты памяти намного выше для более высоких чисел из-за использования функции факультета (!) ... но он демонстрирует вариант теоремы Вильсона в приложении для генерировать все простые числа по алгоритму, реализованному на Python

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)
Штеффен Виттум
источник
4

Используйте генератор простых чисел для создания файла primes.txt, а затем:

class Program
{
    static void Main(string[] args)
    {
        using (StreamReader reader = new StreamReader("primes.txt"))
        {
            foreach (var prime in GetPrimes(10, reader))
            {
                Console.WriteLine(prime);
            }
        }
    }

    public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
    {
        int count = 0;
        string line = string.Empty;
        while ((line = reader.ReadLine()) != null && count++ < upTo)
        {
            yield return short.Parse(line);
        }
    }
}

В этом случае я использую Int16 в сигнатуре метода, поэтому мой файл primes.txt содержит числа от 0 до 32767. Если вы хотите расширить его до Int32 или Int64, ваш файл primes.txt может быть значительно больше.

Дарин Димитров
источник
3
Ссылаясь на OP: «Меня не волнует, какой метод используется (наивный или сито или что-то еще), но я хочу, чтобы он был достаточно коротким и очевидным, как он работает». Я думаю, что мой ответ вполне уместен. Это также самый быстрый способ.
Дарин Димитров
14
Даже если он говорит: «Я не против, какой метод ...», я не думаю, что это включает «открыть список простых чисел». Это было бы похоже на ответ на вопрос «как построить компьютер» «купить компьютер». -1
stevenvh
8
Было бы быстрее, если бы вы действительно написали простые числа в самом исходном коде, вместо того, чтобы читать их из файла.
Дэниел Даранас,
3
Потребляют много памяти? больше, чем чтение полного списка простых чисел в виде текста в ... памяти? Вы знаете, как работают строки в .NET?
jmservera
6
Список простых чисел представляет собой бесконечный, но неизменный список, поэтому имеет смысл использовать предварительно вычисленный список до вероятной верхней границы для приложения. Зачем тратить время на написание кода, который может содержать ошибки, когда есть правильный общедоступный список, который можно использовать для удовлетворения требований.
AndyM
4

Могу предложить следующее решение на C #. Это ни в коем случае не быстро, но очень ясно, что он делает.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    for (int n = 3; n <= limit; n += 2)
    {
        Int32 sqrt = (Int32)Math.Sqrt(n);

        if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
        {
            primes.Add(n);
        }
    }

    return primes;
}

Я пропустил любые проверки - если лимит отрицательный или меньше двух (на данный момент метод всегда будет возвращать как минимум два в качестве простого числа). Но это все легко исправить.

ОБНОВИТЬ

С помощью следующих двух методов расширения

public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        action(item);
    }
}

public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
    for (int i = start; i < end; i += step)
    }
        yield return i;
    }
}

вы можете переписать его следующим образом.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    Range(3, limit, 2)
        .Where(n => primes
            .TakeWhile(p => p <= Math.Sqrt(n))
            .All(p => n % p != 0))
        .Do(n => primes.Add(n));

    return primes;
}

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

Даниэль Брюкнер
источник
Я почти уверен, что вычисление квадратного корня оптимизировано JIT-компилятором (при компиляции с включенной оптимизацией). Вам нужно будет проверить это, изучив сгенерированную сборку (IL оптимизирован только частично и далек от оптимизации, выполняемой JIT-компилятором. Дни подъема цикла и других микро-оптимизаций давно прошли. На самом деле, иногда попытки перехитрить JIT может замедлить ваш код.
Дэйв Блэк,
4

Вот реализация решета Эратосфена на C #:

    IEnumerable<int> GeneratePrimes(int n)
    {
        var values = new Numbers[n];

        values[0] = Numbers.Prime;
        values[1] = Numbers.Prime;

        for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
        {
            values[outer] = Numbers.Prime;

            for (int inner = outer * 2; inner < values.Length; inner += outer)
                values[inner] = Numbers.Composite;
        }

        for (int i = 2; i < values.Length; i++)
        {
            if (values[i] == Numbers.Prime)
                yield return i;
        }
    }

    int FirstUnset(Numbers[] values, int last)
    {
        for (int i = last; i < values.Length; i++)
            if (values[i] == Numbers.Unset)
                return i;

        return -1;
    }

    enum Numbers
    {
        Unset,
        Prime,
        Composite
    }
Алон Губкин
источник
я бы сделал это с помощью bool вместо enum ...
Леттерман
3

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

List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}
jmservera
источник
3

Я знаю, что вы просили о решении, отличном от Haskell, но я включаю его здесь, поскольку он относится к вопросу, а также Haskell прекрасен для этого типа вещей.

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0
гром
источник
Да, я тоже большой поклонник Haskell (если бы я знал это получше)
Дэвид Джонстон
3

Я написал простую реализацию Эратосфена на C # с использованием некоторого LINQ.

К сожалению, LINQ не предоставляет бесконечную последовательность целых чисел, поэтому вам нужно использовать int.MaxValue :(

Мне пришлось кэшировать в анонимном типе кандидат sqrt, чтобы не вычислять его для каждого кешированного простого числа (выглядит немного некрасиво).

Я использую список предыдущих простых чисел до sqrt кандидата

cache.TakeWhile(c => c <= candidate.Sqrt)

и проверяем каждое Int, начиная с 2, против него

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

Вот код:

static IEnumerable<int> Primes(int count)
{
    return Primes().Take(count);
}

static IEnumerable<int> Primes()
{
    List<int> cache = new List<int>();

    var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new 
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

Еще одна оптимизация - избегать проверки четных чисел и возвращать только 2 перед созданием списка. Таким образом, если вызывающий метод просто запрашивает 1 простое число, он избежит беспорядка:

static IEnumerable<int> Primes()
{
    yield return 2;
    List<int> cache = new List<int>() { 2 };

    var primes = Enumerable.Range(3, int.MaxValue - 3)
        .Where(candidate => candidate % 2 != 0)
        .Select(candidate => new
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}
Maghis
источник
1
Мне жаль, что я знал LINQ достаточно, чтобы оценить и лучше понять этот ответ :-) Кроме того, у меня есть ощущение, что это не реализация решета Эратосфена и что он концептуально работает так же, как моя исходная функция (найдите следующий число, которое не делится ни на одно из ранее найденных простых чисел).
Дэвид Джонстон
Да, но «найти следующее число, которое не делится ни на одно из ранее найденных простых чисел (меньшее, чем число)» концептуально похоже на решето эратосфена. Если хотите, я могу немного реорганизовать его, чтобы сделать его более читабельным, даже если вы не знакомы с LINQ. Вы знакомы с итераторами?
Maghis,
Что мне нравится в этом подходе, так это то, что следующее простое число вычисляется именно тогда, когда вызывающий его запрашивает, поэтому такие вещи, как «взять первые n простых чисел» или «взять простые числа, меньшие, чем n», становятся тривиальными
Мэгис,
1
Спасибо, но я могу понять этого достаточно, чтобы более или менее знать, что он делает :-) Мне нравится ленивая оценка, но я бы все равно не назвал это реализацией сита Эратосфена.
Дэвид Джонстон
1

Чтобы сделать его более элегантным, вы должны реорганизовать тест IsPrime в отдельный метод и обрабатывать цикл и приращения за его пределами.

cjk
источник
1

Я сделал это на Java, используя написанную мной функциональную библиотеку, но поскольку моя библиотека использует те же концепции, что и Enumerations, я уверен, что код можно адаптировать:

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});
Винсент Роберт
источник
1

Это самое элегантное, что я могу придумать за короткий срок.

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

Надеюсь, это поможет вам составить представление. Я уверен, что это можно оптимизировать, однако это должно дать вам представление о том, как сделать вашу версию более элегантной.

РЕДАКТИРОВАТЬ: Как отмечалось в комментариях, этот алгоритм действительно возвращает неправильные значения для numberToGenerate <2. Я просто хочу указать, что я не пытался опубликовать ему отличный метод генерации простых чисел (посмотрите на ответ Генри), Я только что указывал, как его метод можно сделать более элегантным.

Давид Божяк
источник
3
Этот возвращает неверный результат для numberToGenerate <2
Питер Смит
Это правда, однако я не разрабатывал алгоритм, я просто показывал ему, как его метод можно сделать более элегантным. Так что эта версия так же неверна, как и та, в которой был задан вопрос.
David Božjak
1
Мне и в голову не приходило, что он сломан для n = 1. Я немного изменил вопрос, чтобы функция работала только при n> 1 :-)
Дэвид Джонстон,
это допускает квадраты простых чисел как простые числа.
Уилл Несс
1

Используя потоковое программирование в Functional Java , я пришел к следующему. Тип Naturalпо существу a BigInteger> = 0.

public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
  { public Stream<Natural> _1()
    { return sieve(xs.tail()._1()
                   .filter($(naturalOrd.equal().eq(ZERO))
                           .o(mod.f(xs.head())))); }}); }

public static final Stream<Natural> primes
  = sieve(forever(naturalEnumerator, natural(2).some()));

Теперь у вас есть значение, которое вы можете носить с собой, а именно бесконечный поток простых чисел. Вы можете делать такие вещи:

// Take the first n primes
Stream<Natural> nprimes = primes.take(n);

// Get the millionth prime
Natural mprime = primes.index(1000000);

// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));

Объяснение сита:

  1. Предположим, что первое число в потоке аргументов - простое, и поместите его в начало возвращаемого потока. Остальная часть обратного потока - это вычисление, которое производится только по запросу.
  2. Если кто-то запрашивает оставшуюся часть потока, вызовите sieve для остальной части потока аргументов, отфильтровывая числа, делящиеся на первое число (остаток от деления равен нулю).

Вам необходимо иметь следующий импорт:

import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
Апокалисп
источник
1

Я лично считаю, что это довольно короткая и чистая (Java) реализация:

static ArrayList<Integer> getPrimes(int numPrimes) {
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    int n = 2;
    while (primes.size() < numPrimes) {
        while (!isPrime(n)) { n++; }
        primes.add(n);
        n++;
    }
    return primes;
}

static boolean isPrime(int n) {
    if (n < 2) { return false; }
    if (n == 2) { return true; }
    if (n % 2 == 0) { return false; }
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) { return false; }
        d += 2;
    }
    return true;
}
Зарконнен
источник
1

Попробуйте этот запрос LINQ, он генерирует простые числа, как вы ожидали

        var NoOfPrimes= 5;
        var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
          .Where(x =>
            {
                 return (x==1)? false:
                        !Enumerable.Range(1, (int)Math.Sqrt(x))
                        .Any(z => (x % z == 0 && x != z && z != 1));
            }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();
РамешВел
источник
1
// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);

// Sequential prime number generator
var primes_ = from n in range
     let w = (int)Math.Sqrt(n)
     where Enumerable.Range(2, w).All((i) => n % i > 0)
     select n;

// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
    Trace.Write(p + ", ");
Trace.WriteLine("");
Радж Пармар
источник
0

Вот пример кода Python, который выводит сумму всех простых чисел меньше двух миллионов:

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum
гром
источник
0

Самый простой метод - это метод проб и ошибок: вы проверяете, делит ли ваше кандидат на простое число n любое число от 2 до n-1.
Первыми ярлыками, конечно, являются: а) вам нужно только проверить нечетные числа и б) вам нужно только проверить делители до sqrt (n).

В вашем случае, когда вы также генерируете все предыдущие простые числа в процессе, вам нужно только проверить, делит ли какое-либо из простых чисел в вашем списке до sqrt (n) n.
Это должно быть самое быстрое, что вы можете получить за свои деньги :-)

редактировать
Хорошо, код, вы его просили. Но я предупреждаю вас :-), это 5-минутный быстрый и грязный код Delphi:

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;
Стивенвх
источник
1
И как это выразить в коде? :-)
Дэвид Джонстон
0

Чтобы узнать первые 100 простых чисел, можно рассмотреть следующий код Java.

int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;

    do
    {

        for (i = 2; i <num; i++)
        {

             int n = num % i;

             if (n == 0) {

             nPrimeCount++;
         //  System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);

             num++;
             break;

             }
       }

                if (i == num) {

                    primeCount++;

                    System.out.println(primeCount + " " + "Prime number is: " + num);
                    num++;
                }


     }while (primeCount<100);
Закир Саджиб
источник
0

Я получил это, впервые прочитав "Решето Аткина" на Wikki, плюс некоторые предыдущие мысли, которые я уделил этому - я трачу много времени на кодирование с нуля и совершенно не понимаю, что люди критически относятся к моему компилятору, очень плотному кодированию style + Я даже не сделал первой попытки запустить код ... многие из парадигм, которые я научился использовать, здесь, просто читайте и плачьте, получите то, что можете.

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

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

Завтра буду работать над своей версией.

package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;

/**
 * May we start by ignores any numbers divisible by two, three, or five
 * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
 * these may be done by hand. Then, with some thought we can completely
 * prove to certainty that no number larger than square-root the number
 * can possibly be a candidate prime.
 */

public class PrimeGenerator<T>
{
    //
    Integer HOW_MANY;
    HashSet<Integer>hashSet=new HashSet<Integer>();
    static final java.lang.String LINE_SEPARATOR
       =
       new java.lang.String(java.lang.System.getProperty("line.separator"));//
    //
    PrimeGenerator(Integer howMany) throws GeneralSecurityException
    {
        if(howMany.intValue() < 20)
        {
            throw new GeneralSecurityException("I'm insecure.");
        }
        else
        {
            this.HOW_MANY=howMany;
        }
    }
    // Let us then take from the rich literature readily 
    // available on primes and discount
    // time-wasters to the extent possible, utilizing the modulo operator to obtain some
    // faster operations.
    //
    // Numbers with modulo sixty remainder in these lists are known to be composite.
    //
    final HashSet<Integer> fillArray() throws GeneralSecurityException
    {
        // All numbers with modulo-sixty remainder in this list are not prime.
        int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
        32,34,36,38,40,42,44,46,48,50,52,54,56,58};        //
        for(int nextInt:list1)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list1");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are  are
        // divisible by three and not prime.
        int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
        //
        for(int nextInt:list2)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list2");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are
        // divisible by five and not prime. not prime.
        int[]list3=new int[]{5,25,35,55};
        //
        for(int nextInt:list3)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list3");//
            }
        }
        // All numbers with modulo-sixty remainder in
        // this list have a modulo-four remainder of 1.
        // What that means, I have neither clue nor guess - I got all this from
        int[]list4=new int[]{1,13,17,29,37,41,49,53};
        //
        for(int nextInt:list4)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list4");//
            }
        }
        Integer lowerBound=new Integer(19);// duh
        Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
        int upperBound=upperStartingPoint.intValue();//
        HashSet<Integer> resultSet=new HashSet<Integer>();
        // use a loop.
        do
        {
            // One of those one liners, whole program here:
            int aModulo=upperBound % 60;
            if(this.hashSet.contains(new Integer(aModulo)))
            {
                continue;
            }
            else
            {
                resultSet.add(new Integer(aModulo));//
            }
        }
        while(--upperBound > 20);
        // this as an operator here is useful later in your work.
        return resultSet;
    }
    // Test harness ....
    public static void main(java.lang.String[] args)
    {
        return;
    }
}
//eof
Николас Джордан
источник
0

Попробуйте этот код.

protected bool isPrimeNubmer(int n)
    {
        if (n % 2 == 0)
            return false;
        else
        {
            int j = 3;
            int k = (n + 1) / 2 ;

            while (j <= k)
            {
                if (n % j == 0)
                    return false;
                j = j + 2;
            }
            return true;
        }
    }
    protected void btn_primeNumbers_Click(object sender, EventArgs e)
    {
        string time = "";
        lbl_message.Text = string.Empty;
        int num;

        StringBuilder builder = new StringBuilder();

        builder.Append("<table><tr>");
        if (int.TryParse(tb_number.Text, out num))
        {
            if (num < 0)
                lbl_message.Text = "Please enter a number greater than or equal to 0.";
            else
            {
                int count = 1;
                int number = 0;
                int cols = 11;

                var watch = Stopwatch.StartNew();

                while (count <= num)
                {
                    if (isPrimeNubmer(number))
                    {
                        if (cols > 0)
                        {
                            builder.Append("<td>" + count + " - " + number + "</td>");
                        }
                        else
                        {
                            builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
                            cols = 11;
                        }
                        count++;
                        number++;
                        cols--;
                    }
                    else
                        number++;
                }
                builder.Append("</table>");
                watch.Stop();
                var elapsedms = watch.ElapsedMilliseconds;
                double seconds = elapsedms / 1000;
                time = seconds.ToString();
                lbl_message.Text = builder.ToString();
                lbl_time.Text = time;
            }
        }
        else
            lbl_message.Text = "Please enter a numberic number.";

        lbl_time.Text = time;

        tb_number.Text = "";
        tb_number.Focus();
    }

Вот код aspx.

<form id="form1" runat="server">
    <div>
        <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>

        <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
        </p>
        <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
        <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
    </div>
</form>

Результаты: 10000 простых чисел менее чем за секунду

100000 простых чисел за 63 секунды

Скриншот первых 100 простых чисел введите описание изображения здесь

риз
источник
1
Попробовав его, я смог оценить его эффективность и подачу результатов: пожалуйста, аргументируйте его элегантность.
Greybeard
Стиль результата - это всего лишь дополнительная часть. Позвольте мне обсудить алгоритм возврата истинного / ложного в виде простого числа. n% 2 удалит половину чисел, потому что четное число всегда делится на 2. В коде else я делю только на нечетные числа, увеличивая делимое на два (так что следующее делимое также нечетное) до половины этого числа, которое является простым. или нет. Почему половина, чтобы не терять время, потому что это даст нам дробный ответ.
риз
log10 (63) ~ = 1.8, т.е. ваши данные показывают темп роста n ^ 1.8. Это очень медленно; оптимальное решето реализаций Эратосфена exibit ~ n ^ 1.01..1.05; оптимальное пробное деление ~ n ^ 1.35..1.45. Вы isPrimeNubmerдействительно реализуете неоптимальное тройное деление; его асимптотика ухудшится примерно до n ^ 2 (или даже выше), когда вы попытаетесь сгенерировать еще больше простых чисел.
Уилл Несс,