Самый элегантный способ генерировать простые числа
Какой самый элегантный способ реализовать эту функцию:
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)
- Очень чистая реализация сита Eratosthenes (starblue)
- Используйте Java
BigIntegerс иnextProbablePrimeдля очень простого кода, хотя я не могу себе представить, что он особенно эффективен (dfa) - Используйте LINQ, чтобы лениво генерировать список простых чисел (Магис)
- Поместите много простых чисел в текстовый файл и прочитайте их при необходимости (Дарин)
Редактировать 2: я реализовал в C# несколько методов, приведенных здесь, и другой метод, не упомянутый здесь. Все они эффективно находят первые n простых чисел (и у меня есть приличный метод нахождения предела для сит).
25 ответов
Большое спасибо всем, кто дал полезные ответы. Вот мои реализации нескольких различных методов поиска первых 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] или так далее.
Сито Эратосфена ( голубоватое)
Это находит все простые числа к. Чтобы составить список первых 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;
}
Используйте оценку
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();
}
Вы на правильном пути.
Некоторые комментарии
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<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;
}
На самом деле это всего лишь разновидность некоторых постов с более приятным форматированием.
Авторские права 2009 - St.Wittum 13189, Берлин, ГЕРМАНИЯ, лицензия CC-BY-SA, https://creativecommons.org/licenses/by-sa/3.0/
Простой, но самый элегантный способ вычисления ВСЕХ ПРАЙМОВ был бы таким, но этот способ медленный и затраты памяти гораздо выше для больших чисел, потому что используется функция faculty (!)... но она демонстрирует изменение теоремы Вильсона в приложении к генерировать все простые числа по алгоритму, реализованному в Python
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
Я могу предложить следующее решение 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;
}
Он менее эффективен (потому что квадратный корень пересматривается довольно часто), но это даже более чистый код. Можно переписать код, чтобы лениво перечислять простые числа, но это немного загромождает код.
Используйте генератор простых чисел для создания 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 может быть значительно больше.
Я знаю, что вы просили решение, не относящееся к 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
Вот реализация Sieve of Eratosthenes в 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
}
Используя тот же алгоритм, вы можете сделать это немного короче:
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);
}
Я написал простую реализацию Eratosthenes на 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;
}
}
// 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("");
Чтобы сделать его более элегантным, вы должны реорганизовать свой тест IsPrime в отдельный метод и обрабатывать циклы и приращения за пределами этого.
Попробуйте этот запрос 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();
Это самое элегантное, что я могу придумать за короткое время.
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. Я просто хочу отметить, что я не пытался опубликовать его отличный метод для генерации простых чисел (посмотрите на ответ Анри), Я просто указывал, как его метод можно сделать более элегантным.
Вот пример кода 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
Я сделал это на 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;
}
});
}
});
Используя потоковое программирование в функциональной 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;
}
Я получил это, впервые прочитав "Sieve of Atkin" в Вики, плюс некоторую предварительную мысль, которую я уделил этому - я трачу много времени на программирование с нуля и полностью обнуляю людей, критикующих мой компиляторный, очень плотный код. стиль + Я даже не делал первой попытки запустить код... многие из парадигм, которые я научился использовать, здесь, просто читайте и плачьте, получите то, что можете.
Будьте абсолютно и абсолютно уверены, что действительно все это протестировали перед любым использованием, наверняка не показывайте это никому - это для чтения и рассмотрения идей. Мне нужно, чтобы работал инструмент первичности, поэтому я начинаю каждый раз, когда мне нужно, чтобы что-то работало.
Получить одну чистую компиляцию, а затем начать убирать то, что неисправно - у меня есть почти 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
Простейшим методом является метод проб и ошибок: вы пытаетесь, если любое число от 2 до n-1 делит вашего кандидата на простое число n.
Первые ярлыки - это, конечно, а) вам нужно только проверять нечетные числа, и б) вам нужно только проверить делители до sqrt(n).
В вашем случае, когда вы также генерируете все предыдущие простые числа в этом процессе, вам нужно только проверить, делит ли 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 <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);
Попробуйте этот код.
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 простых чисел