Самый элегантный способ генерации простых чисел [закрыто]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каков наиболее элегантный способ реализации этой функции:
ArrayList generatePrimes(int n)
Эта функция генерирует первый n простые числа (править:где 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;
}
Меня не слишком беспокоит скорость, хотя я не хочу, чтобы она была явно неэффективной.Меня не волнует, какой метод используется (наивный, сито или что-то еще), но я хочу, чтобы он был достаточно кратким и очевидным, как он работает.
Редактировать:Спасибо всем, кто ответил, хотя многие не ответили на мой актуальный вопрос.Еще раз повторю: мне нужен был красивый и понятный фрагмент кода, который генерировал бы список простых чисел.Я уже знаю, как это сделать разными способами, но склонен писать код, который не так ясен, как мог бы быть.В этой теме было предложено несколько хороших вариантов:
- Улучшенная версия того, что у меня было изначально (Питер Смит, jmservera и Rekreativc)
- Очень чистая реализация решета Эратосфена (звездно-синее)
- Используйте Java
BigIntegerпесокnextProbablePrimeдля очень простого кода, хотя я не могу себе представить, чтобы он был особенно эффективным (dfa) - Используйте LINQ для ленивого создания списка простых чисел (Магис)
- Поместите множество простых чисел в текстовый файл и читайте их, когда это необходимо (дарин)
Редактировать 2:у меня есть реализовано на С# несколько методов, приведенных здесь, и еще один метод, здесь не упомянутый.Все они находят первое н эффективно заправляет (и у меня есть достойный метод поиска предела подачи на сита).
Решение 2
Большое спасибо всем, кто дал полезные ответы.Вот мои реализации нескольких различных методов поиска первого н простые числа в C#.Первые два метода в значительной степени соответствуют тому, что было опубликовано здесь.(Названия плакатов указаны рядом с заголовком.) Я планирую когда-нибудь провести решето Аткина, хотя подозреваю, что это будет не так просто, как методы, представленные здесь сейчас.Если кто-нибудь видит способ улучшить любой из этих методов, мне бы хотелось знать :-)
Стандартный метод (Питер Смит, jmservera, Рекреативц)
Первое простое число — 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] или скоро.
Решето Эратосфена (звездно-голубой)
Это находит все простые числа к.Чтобы составить список первых н простые числа, нам сначала нужно приблизительно оценить значение нй премьер.Следующий метод, как описано здесь, Означает ли это.
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;
}
Другие советы
Используйте оценку
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;
}
Возвращаюсь к старому вопросу, но я наткнулся на него, играя с 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();
}
Вы на хорошем пути.
Некоторые комментарии
простые числа.Добавить(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<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);
}
}
Ни в коем случае не эффективный, но, возможно, самый читабельный:
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;
}
На самом деле это всего лишь вариация некоторых постов здесь с более приятным форматированием.
Я знаю, что вы просили решение, отличное от 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
Используйте простой генератор чисел чтобы создать 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 может быть значительно больше.
Я могу предложить следующее решение на C#.Это ни в коем случае не быстро, но очень ясно, что он делает.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
for (int n = 3; n <= limit; n += 2)
{
Int32 sqrt = (Int32)Math.Sqrt(n);
if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
{
primes.Add(n);
}
}
return primes;
}
Я исключил любые проверки - если предел отрицателен или меньше двух (на данный момент метод всегда будет возвращать как минимум два в качестве простого числа).Но это все легко исправить.
ОБНОВЛЯТЬ
Со следующими двумя методами расширения
public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
foreach (T item in collection)
{
action(item);
}
}
public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
for (int i = start; i < end; i += step)
}
yield return i;
}
}
вы можете переписать его следующим образом.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
Range(3, limit, 2)
.Where(n => primes
.TakeWhile(p => p <= Math.Sqrt(n))
.All(p => n % p != 0))
.Do(n => primes.Add(n));
return primes;
}
Это менее эффективно (поскольку квадратный корень довольно часто пересчитывается), но это даже более чистый код.Можно переписать код для ленивого перечисления простых чисел, но это немного загромождает код.
Вот реализация Решето Эратосфена в С#:
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
}
Авторские права принадлежат St.Wittum 13189 Berlin, ГЕРМАНИЯ, 2009 г., по лицензии 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)
Используя тот же алгоритм, вы можете сделать это немного короче:
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);
}
Я написал простую реализацию Эратосфена на C#, используя LINQ.
К сожалению, LINQ не предоставляет бесконечную последовательность целых чисел, поэтому вам придется использовать int.MaxValue:(
Мне пришлось кэшировать кандидат sqrt в анонимном типе, чтобы не вычислять его для каждого кэшированного простого числа (выглядит немного некрасиво).
Я использую список предыдущих простых чисел до sqrt кандидата
cache.TakeWhile(c => c <= candidate.Sqrt)
и проверьте каждый Int, начиная с 2, против него
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Вот код:
static IEnumerable<int> Primes(int count)
{
return Primes().Take(count);
}
static IEnumerable<int> Primes()
{
List<int> cache = new List<int>();
var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Другая оптимизация — избегать проверки четных чисел и возвращать только 2 перед созданием списка.Таким образом, если вызывающий метод просто запрашивает 1 простое число, это позволит избежать всего беспорядка:
static IEnumerable<int> Primes()
{
yield return 2;
List<int> cache = new List<int>() { 2 };
var primes = Enumerable.Range(3, int.MaxValue - 3)
.Where(candidate => candidate % 2 != 0)
.Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Чтобы сделать его более элегантным, вам следует провести рефакторинг теста IsPrime в отдельный метод и обрабатывать циклы и приращения за его пределами.
Я сделал это на 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;
}
});
}
});
Вот пример кода 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;
}
Надеюсь, это поможет вам получить представление.Я уверен, что это можно оптимизировать, однако это должно дать вам представление о том, как можно сделать вашу версию более элегантной.
РЕДАКТИРОВАТЬ: Как отмечалось в комментариях, этот алгоритм действительно возвращает неправильные значения для numberToGenerate <2.Я просто хочу отметить, что я не пытался опубликовать ему отличный метод генерации простых чисел (посмотрите на ответ Анри), я просто указывал, как можно сделать его метод более элегантным.
Использование потокового программирования в Функциональная 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;
Лично я считаю, что это довольно короткая и чистая реализация (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;
}
Попробуйте этот запрос 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();
// 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("");
Самый простой метод – метод проб и ошибок:вы пытаетесь проверить, делит ли какое-либо число от 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;
Чтобы узнать первые 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);
Я получил это, впервые прочитав «Решето Аткина» на Викики, а также некоторые предварительные размышления, которые я дал по этому поводу — я трачу много времени на программирование с нуля и совершенно не обращаю внимания на людей, критикующих мой компиляторный, очень плотный код. стиль + я даже не сделал первой попытки запустить код...многие из парадигм, которые я научился использовать, находятся здесь, просто читайте и плачьте, получайте то, что можете.
Будьте абсолютно и абсолютно уверены, что действительно протестируете все это перед любым использованием, и ни в коем случае не показывайте это никому - это для чтения и обдумывания идей.Мне нужно, чтобы инструмент 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
Попробуйте этот код.
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 простых чисел менее чем за одну секунду
100 000 простых чисел за 63 секунды
Скриншот первых 100 простых чисел
