Вопрос по c#, java, algorithm – Самый элегантный способ генерации простых чисел [закрыто]

81

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

<code>ArrayList generatePrimes(int n)
</code>

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

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

<code>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;
}
</code>

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

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

A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc) A very clean implementation of the sieve of Eratosthenes (starblue) Use Java's BigIntegers and nextProbablePrime for very simple code, although I can't imagine it being particularly efficient (dfa) Use LINQ to lazily generate the list of primes (Maghis) Put lots of primes in a text file and read them in when necessary (darin)

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

Нет, и это также не для Project Euler :-) David Johnstone
это домашнее задание? Erich Kitzmueller
было бы лучше, если бы я отступил от имени & lt; int & gt; и уступая один за другим Felice Pollano
Что я хотел бы знать, что этоleast элегантный способ генерировать простые числа. Я думаю о чем-то, касающемся базы данных Access? j_random_hacker
для сравнения2008 Haskell code by BMeph: nubBy (((>1).).gcd) [2..], Он оставляет только недвойственные числа среди натуральных чисел, начиная с 2, считая дубликатом любое число,gcd с любым из ранее найденных чисел больше 1. Это очень неэффективно, квадратично по числу произведенных простых чисел. Но этоelegant. Will Ness

Ваш Ответ

25   ответов
47

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

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;
}
не достаточно зацикливаться, покаi <= Math.sqrt(limit) во внешнем цикле? Christoph
@ David Johnstone Нет, pi (n) = n / log (n) недооценивает число простых чисел до n, что идет в обратном направлении. Я рад, что вы нашли гораздо более приятное приближение. starblue
ЗаменяяBitSet классом, реализующим факторизацию колес для 2, 3 и 5, он становится почти в 3 раза быстрее. starblue
Это очень хорошая реализация решетки Эратосфена David Johnstone
Если вы хотите удалить все кратные 2 в своем собственном цикле, вы можете использовать j + = 2 * i в качестве приращения цикла, чтобы сэкономить дополнительное время выполнения, и вы можете рассчитать это один раз, используя сдвиг битов Nick Larsen♦
34

кто дал полезные ответы. Вот мои реализации нескольких различных методов поиска первого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] илискор.

Сито Эратосфена ( Starblue)

Это находит все простые числа для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 ++)», чтобы предотвратить переполнение. Repo Man
Эта реализация Решета Сундарама - одна из немногих правильных. Большинство из них используют неправильные оценки для i и j при расчетеi+j+2*i*j приводит к неправильному выводу. jahackbeth
1

который выводит сумму всех простых чисел менее двух миллионов:

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
9

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

Primes.Add (3); делает, что эта функция не работает для числа = 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;
}
тестирование простого * prime <= curTest в цикле вместо предварительного вычисления квадратного корня, вероятно, сделает его быстрее и сделает его более общим (будет работать для больших чисел и т. д.) yairchu
Зачем использовать квадратный корень? Каков математический фон для такого варианта? Я, вероятно, тупо, разделил бы только на 2. Luis Filipe
Потому что если число имеет простые факторы, по крайней мере один из них должен быть меньше или равен квадратному корню. Если a * b = c и a <= b, то a <= sqrt (c) <= b. David Johnstone
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);
    }
}
Миллер-Раввин очень быстрый и очень простой код. Предоставление достаточного количества итераций делает его достаточно надежным, чтобы конкурировать со случайным отказом ЦП с точки зрения вероятности ложного срабатывания. Недостатком алгоритма является то, что понять, почему он на самом деле работает, является сложной задачей. Brian
1

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

1

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

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;
            }
        });
    }
});
11

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

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();
}
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;
}

На самом деле это всего лишь разновидность некоторых постов с более приятным форматированием.

4

что вы просили решение, не относящееся к 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
Да, я тоже большой фанат Хаскелла (просто хотелось бы, чтобы я знал это лучше) David Johnstone
4

https: //creativecommons.org/licenses/by-sa/3.0

Простой, но самый элегантный способ вычисления ВСЕХ ПРАЙМОВ был бы таким, но этот способ медленный и затраты памяти намного выше для больших чисел, потому что используется функция faculty (!) ... но она демонстрирует изменение теоремы Вильсона в приложении генерировать все простые числа по алгоритму, реализованному в Pytho

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)
4

о, но очень ясно о том, что он делает.

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 можетпомедленне ваш код Dave Black
0

впервые прочитав «Sieve of Atkin» в Вики, плюс некоторую предварительную мысль, которую я уделил этому - я трачу много времени на программирование с нуля и полностью обнуляю людей, критикующих мой компилятор, очень плотный стиль кодирования + Я даже не делал первой попытки запустить код ... многие из парадигм, которые я научился использовать, здесь, просто читайте и плачьте, получите то, что можете.

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

Получите одну чистую компиляцию, а затем начните убирать то, что неисправно - у меня почти 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
1

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
// 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

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

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

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

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;
А как ты это выражаешь в коде? : -) David Johnstone
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 может быть значительно больше.

Цитируя ОП: «Я не возражаю против того, какой метод используется (наивный или сито или что-то еще), но я хочу, чтобы он был довольно коротким и очевидным, как он работает». Я думаю, что мой ответ совершенно актуален. Это также самый быстрый метод. Darin Dimitrov
Даже если он говорит: «Я не против того, какой метод ...», я не думаю, что это включает «открыть список простых чисел». Это все равно, что ответить на вопрос «как построить компьютер» на «купить компьютер». -1 stevenvh
Было бы быстрее, если бы вы на самом деле писали простые числа в самом исходном коде, а не читали их из файла. Daniel Daranas
Дорогой, о дорогой .. Harry Lime
Список простых чисел - это бесконечный, но неизменный список, поэтому имеет смысл использовать предварительно вычисленный список до вероятной верхней границы приложения. Зачем тратить время на написание кода, который может содержать ошибки, когда есть правильный общедоступный список, который можно использовать для удовлетворения требований. AndyM
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 ... Letterman
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);
}
3

торого 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;
    }
}
Спасибо, но я могу понять, что достаточно, чтобы более или менее знать, что он делает :-) Мне нравится ленивая оценка, но я все равно не назвал бы это реализацией решета Эратосфена. David Johnstone
Хотелось бы, чтобы я знал LINQ достаточно, чтобы лучше понять и понять этот ответ :-) Кроме того, у меня есть ощущение, что это не реализация решета Эратосфена, и что он концептуально работает так же, как моя первоначальная функция (найдите следующее число, которое не делится ни на одно из ранее найденных простых чисел). David Johnstone
Да, но «найти следующее число, которое не делится ни на одно из ранее найденных простых чисел (меньше числа)», концептуально похоже на сито эратосфена. Если хотите, я могу немного изменить его, чтобы сделать его более читабельным, даже если вы не знакомы с LINQ. Вы знакомы с итераторами? Maghis
Что мне нравится в этом подходе, так это то, что следующее простое число вычисляется только тогда, когда его запрашивает вызывающий, поэтому такие вещи, как «взять первые n простых чисел» или «взять простые числа, меньшие n», становятся тривиальными Maghis
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. Я просто хочу отметить, что я не пытался опубликовать ему отличный метод для генерации простых чисел (см. Ответ Анри), я просто указывал, как его метод можно сделать более элегантным.

Этот возвращает неверный результат для numberToGenerate <2 Peter Smit
Это правда, однако я не разрабатывал алгоритм, я просто показывал ему, как его метод можно сделать более элегантным. Так что эта версия в равной степени ошибочна, как и в первом вопросе. David Božjak
Мне не пришло в голову, что он сломался для n = 1. Я немного изменил вопрос, чтобы функция работала только при n> 1: -) David Johnstone
это допускает квадраты простых чисел как простые числа. Will Ness
1

Использование потокового программирования в Функциональная Java, Я придумал следующее. ТипNatural по сути является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));

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

Предположим, что первое число в потоке аргументов является простым, и поместите его в начало обратного потока. Остальная часть обратного потока - это вычисление, которое будет производиться только по запросу. Если кто-то запрашивает остаток потока, вызовите 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

он генерирует простые числа, как вы ожидали

        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();
0

можно рассмотреть следующий код 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

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

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" run,at="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>

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

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

Скриншот первых 100 простых чисел

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

Похожие вопросы