Самый элегантный способ генерации простых чисел

Ответ 1

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

Стандартный метод (Питер Смит, 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;
}

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

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

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

Ответ 2

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

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

Повторное рассмотрение старого вопроса, но я наткнулся на него во время игры с 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(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();
}

Ответ 4

Вы находитесь на хорошем пути.

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

• 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;
}

Ответ 5

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

Для полноты вы можете просто использовать 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);
    }
}

Ответ 6

Используйте простой генератор чисел для создания 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 может быть значительно большим.

Ответ 7

Я знаю, что вы попросили решения, отличные от 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

Ответ 8

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

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

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

UPDATE

Используйте следующие два метода расширения

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

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

Ответ 9

Здесь реализована реализация Сито Eratosthenes в С#:

    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
    }

Ответ 10

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

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

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

Ответ 11

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

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

Ответ 12

Авторские права 2009 by St.Wittum 13189 Berlin GERMANY под лицензией 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)

Ответ 13

Я написал простую реализацию Eratosthenes в С#, используя некоторый LINQ.

К сожалению, LINQ не предоставляет бесконечную последовательность int, поэтому вам нужно использовать 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;
    }
}

Ответ 14

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

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

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

EDIT: Как отмечено в комментариях, этот алгоритм действительно возвращает неправильные значения для numberToGenerate < 2. Я просто хочу указать, что я не пытался опубликовать ему отличный метод для генерации простых чисел (посмотрите на ответ Анри для этого), я злобно указывал, как его метод можно сделать более элегантным.

Ответ 15

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

Ответ 16

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

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

Ответ 17

Вот пример кода 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

Ответ 18

Используя потоковое программирование в Функциональная 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));

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

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

У вас должен быть следующий импорт:

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;

Ответ 19

Я лично считаю, что это довольно короткая и чистая (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;
}

Ответ 20

Попробуйте этот запрос 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();

Ответ 21

// 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("");

Ответ 22

Самый простой метод - это пробная версия и ошибка: вы пытаетесь, если любое число между 2 и n-1 делит ваш кандидат на n. Первые ярлыки, конечно, a) вам нужно только проверять нечетные числа, и b) вы можете проверить только делители до 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;

Ответ 23

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

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

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

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

package demo;
// This code is a discussion of an opinion in a technical forum.
// It 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

Ответ 24

Чтобы узнать первые 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);

Ответ 25

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

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 простых номеров