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

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

ArrayList generatePrimes(int n) 

Эта функция генерирует первые n простых чисел (edit: where n>1 ), поэтому generatePrimes(5) возвращает ArrayList с {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; } 

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

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

  • Более приятная версия того, что я изначально имел (Peter Smit, jmservera и Rekreativc)
  • Очень чистая реализация сита Эратосфена (starblue)
  • Используйте Java BigInteger s и nextProbablePrime для очень простого кода, хотя я не могу себе представить, что он особенно эффективен (dfa)
  • Используйте LINQ для ленивого генерации списка простых чисел (Maghis)
  • Поместите много простых в текстовый файл и прочитайте их, когда это необходимо (дарин)

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

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

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

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

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

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

 public static List GeneratePrimesNaive(int n) { List primes = new List(); 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 простых чисел, сначала нужно приблизиться к значению nth prime. Следующий способ, как описано здесь , делает это.

 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 GeneratePrimesSieveOfEratosthenes(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfEratosthenes(limit); List primes = new List(); 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 GeneratePrimesSieveOfSundaram(int n) { int limit = ApproximateNthPrime(n); BitArray bits = SieveOfSundaram(limit); List primes = new List(); 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; } 

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

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

 public List 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(); } 

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

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

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

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

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

 public class PrimeGenerator implements Iterator, Iterable { 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 iterator() { return this; } } @Test public void printPrimes() { for (BigInteger p : new PrimeGenerator()) { System.out.println(p); } } 

Ни в коем случае не эффективный, но, возможно, самый читаемый:

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

с:

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

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

Я знаю, что вы попросили решения, отличные от 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 np = n `mod` p == 0 

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

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

 public static List GetPrimes(Int32 limit) { List primes = new List() { 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(this IEnumerable collection, Action action) { foreach (T item in collection) { action(item); } } public static IEnumerable Range(Int32 start, Int32 end, Int32 step) { for (int i = start; i < end; i += step) } yield return i; } } 

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

 public static List GetPrimes(Int32 limit) { List primes = new List() { 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; } 

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

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

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

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

 List primes=new List(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); } 

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

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

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

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

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

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

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

Вот код:

 static IEnumerable Primes(int count) { return Primes().Take(count); } static IEnumerable Primes() { List cache = new List(); 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 Primes() { yield return 2; List cache = new List() { 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; } } 

Авторские права 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) 

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

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

 Iterable numbers = new Range(1, 100); Iterable primes = numbers.inject(numbers, new Functions.Injecter, Integer>() { public Iterable call(Iterable 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() { public Boolean call(Integer n) throws Exception { return n > number && n % number == 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 

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

 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. Я просто хочу указать, что я не пытался опубликовать его отличный метод для генерации простых чисел (посмотрите на ответ Генри для этого), Я злобно указывал, как его метод можно сделать более элегантным.

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

 public static Stream sieve(final Stream xs) { return cons(xs.head(), new P1>() { public Stream _1() { return sieve(xs.tail()._1() .filter($(naturalOrd.equal().eq(ZERO)) .o(mod.f(xs.head())))); }}); } public static final Stream primes = sieve(forever(naturalEnumerator, natural(2).some())); 

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

 // Take the first n primes Stream nprimes = primes.take(n); // Get the millionth prime Natural mprime = primes.index(1000000); // Get all primes less than n Stream pltn = primes.takeWhile(naturalOrd.lessThan(n)); 

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

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

Необходимо импортировать следующие товары:

 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; 

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

 static ArrayList getPrimes(int numPrimes) { ArrayList primes = new ArrayList(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; } 

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

  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(); 
 // Create a test range IEnumerable 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(""); 

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

В вашем случае, когда вы также генерируете все предыдущие простые числа в этом процессе, вам нужно только проверить, не разделяет ли ни один из простых чисел в вашем списке, вплоть до sqrt (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; 

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

 int num = 2; int i, count; int nPrimeCount = 0; int primeCount = 0; do { for (i = 2; i  

Я получил это в первом чтении «Сито Аткина» по 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 { // Integer HOW_MANY; HashSethashSet=new HashSet(); 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 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 resultSet=new HashSet(); // 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 

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

 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(""); 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(""); } else { builder.Append(""); cols = 11; } count++; number++; cols--; } else number++; } builder.Append("
" + count + " - " + number + "
" + count + " - " + number + "
"); 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(); }

Here is the aspx code.

 

Please enter a number:

Results: 10000 Prime Numbers in less than one second

100000 Prime Numbers in 63 seconds

Screenshot of first 100 Prime Numbers введите описание изображения здесь

Interesting Posts

ориентация экрана для Android

Как я могу определить, какой пользователь в настоящее время входит в систему Windows 7?

Почему мы не можем отключить брандмауэр и обмен файлами?

Как я могу анализировать проблемы производительности до / во время процесса входа в систему?

Не удается найти Theme.AppCompat.Light для новой поддержки Android ActionBar

Различные легенды и цвета заливки для граненых ggplot?

Синтаксис инициализатора вложенных объектов

Почему локальная переменная elisp сохраняет свою ценность в этом случае?

Как я могу объединить два объекта JObject?

Сравните значения двух массивов – classического asp

Переустановка Windows 8 из Dreamspark

Вентилятор центрального процессора Sony Vaio работает на полной скорости после установки предварительного просмотра Windows 8.1

Интерференция при установке Windows XP

Какова наиболее эффективная библиотека compilationов Java?

AES algo – проблема с расшифровкой

Давайте будем гением компьютера.