A maioria maneira elegante para gerar números primos [fechado]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O que é a maneira mais elegante para implementar esta função:
ArrayList generatePrimes(int n)
Esta função gera os primeiros números primos n (EDIT: onde n>1), de modo generatePrimes(5) retornará um ArrayList com {2, 3, 5, 7, 11}. (Eu estou fazendo isso em C #, mas estou feliz com uma implementação Java - ou qualquer outra linguagem semelhante para que o assunto (por isso não Haskell)).
Eu sei como escrever esta função, mas quando eu fiz isso ontem à noite que não acabam tão agradável como eu estava esperando. Aqui está o que eu vim com:
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;
}
Eu não estou muito preocupado com a velocidade, embora eu não quero que seja obviamente ineficiente. Eu não me importo qual método é usado (ingênuo ou peneira ou qualquer outra coisa), mas eu quero que ele seja bastante curto e óbvio como ele funciona.
Editar : Obrigado a todos que responderam, embora muitos não respondeu a minha pergunta real. Para reiterar, eu queria um pedaço limpo agradável do código que gerou uma lista de números primos. Eu já sei como fazê-lo um monte de maneiras diferentes, mas estou propenso a escrever código que não é tão claro quanto poderia ser. Neste segmento foram propostas algumas opções boas:
- A versão mais agradável do que eu tinha originalmente (Peter Smit, jmservera e Rekreativc)
- Uma execução muito limpo do crivo de Eratóstenes (Starblue)
-
BigIntegers enextProbablePrimede usar Java de código muito simples, embora eu não posso imaginar que seja particularmente eficiente (DFA) - Use LINQ para gerar preguiçosamente a lista de números primos (Maghis)
- Coloque lotes de números primos em um arquivo de texto e lê-los quando necessário (Darin)
Editar 2 : Eu tenho implementado em C # um par dos métodos indicados aqui, e um outro método não mencionado aqui. Todos eles encontrar a primeira n primos efetivamente (e eu tenho um método decente de encontrar o limite para fornecer para as peneiras).
Solução 2
Muito obrigado a todos os que deram respostas úteis. Aqui estão as minhas implementações de alguns métodos diferentes de encontrar o primeiro n primos em C #. Os dois primeiros métodos são muito bonito o que foi publicado aqui. (Os nomes cartazes estão ao lado do título.) Estou pensando em fazer a peneira de Atkin em algum momento, embora eu suspeito que não será tão simples como os métodos aqui atualmente. Se alguém pode ver nenhuma maneira de melhorar qualquer um destes métodos que eu adoraria saber: -)
Método Padrão ( Peter Smit , jmservera , Rekreativc )
O primeiro número primo é 2. Adicione isto a uma lista de números primos. O primeiro seguinte é o próximo número que não é divisível por qualquer número nesta lista.
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;
}
Esta foi optimizada por apenas a testar para divisibilidade-se à raiz quadrada do número a ser testado; e por apenas um teste de números ímpares. Isto pode ser ainda mais optimizado por meio de testes apenas para os números da 6k+[1, 5] forma, ou 30k+[1, 7, 11, 13, 17, 19, 23, 29] ou assim por diante .
Crivo de Eratóstenes ( starblue )
isto encontra todos os números primos para k . Para fazer uma lista do primeiro n primos, precisamos primeiro valor aproximado do n th prime. O método, como descrito aqui , faz isso.
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;
}
Peneira de Sundaram
Eu só descobriu este peneira recentemente, mas ele pode ser implementado simplesmente. Minha implementação não é tão rápido como o Crivo de Eratóstenes, mas é significativamente mais rápido do que o método ingênuo.
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;
}
Outras dicas
Use a estimativa
pi(n) = n / log(n)
para o número de números primos até n para encontrar um limite, e então usar uma peneira. A estimativa subestima o número de números primos até N pouco, de modo que o crivo irá ser ligeiramente maior do que o necessário, o que é ok.
Esta é a minha peneira Java padrão, calcula o primeiro milhão de primos em cerca de um segundo em um laptop normal:
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;
}
Ressuscitando uma questão antiga, mas eu tropecei sobre ele enquanto brincava com LINQ.
Esse código requer .NET4.0 ou NET3.5 Com extensões paralelas
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();
}
Você está no bom caminho.
Alguns comentários
-
primes.Add (3); faz que esta função não funciona para number = 1
-
Você dont't tem que testar a divisão com primenumbers maiores que o squareroot do número a ser testado.
código sugerido:
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;
}
você deve dar uma olhada primos prováveis ??. Em particular, ter um olhar para Randomized Algoritmos e Miller-Rabin teste de primalidade .
Por uma questão de exaustividade você pode simplesmente usar 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);
}
}
De maneira nenhuma effecient, mas talvez o mais legível:
public static IEnumerable<int> GeneratePrimes()
{
return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
.All(divisor => candidate % divisor != 0));
}
com:
public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
for (int i = from; i <= to; i++) yield return i;
}
Na verdade apenas uma variação de alguns posts aqui com mais agradável formatação.
Eu sei que você pediu solução não Haskell, mas estou incluindo este aqui como ele se relaciona com a questão e também Haskell é bonito para este tipo de coisa.
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
Aqui está uma implementação de Crivo de Eratóstenes em 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
}
Copyrights 2009 por St.Wittum 13189 Berlin ALEMANHA abaixo CC-BY-SA Licença https://creativecommons.org/licenses/by-sa/3.0/
O simples, mas maneira mais elegante para calcular todos os primos seria isso, mas desta forma é lento e os custos de memória são muito mais elevados para os números mais elevados porque o uso da faculdade de função (!) ... mas demonstra uma variação de Wilson théorème em uma aplicação para gerar todos os primos por algoritmo implementado em Python
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
Usando o mesmo algoritmo que você pode fazê-lo um pouco menor:
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);
}
Eu escrevi uma implementação simples Eratóstenes em c # usando alguns LINQ.
Infelizmente LINQ não fornece uma sequência infinita de inteiros então você tem que usar int.MaxValue: (
Eu tive que cache um tipo anonimous o sqrt candidato para evitar a calculá-lo para cada principais em cache (parece um pouco feio).
Eu uso uma lista de números primos anteriores até sqrt do candidato
cache.TakeWhile(c => c <= candidate.Sqrt)
e verificar cada Int a partir de 2 contra ele
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Aqui está o código:
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;
}
}
Outra otimização é para evitar a verificação de números pares e retornar apenas 2 antes de criar a lista. Dessa forma, se o método chamando apenas pede um nobre que vai evitar toda a confusão:
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;
}
}
Para torná-lo mais elegante, você pode refazer o seu teste IsPrime em um método separado, e lidar com os e incrementos looping fora disso.
Eu fiz isso em Java usando uma biblioteca funcional eu escrevi, mas desde a minha biblioteca utiliza os mesmos conceitos como enumerações, estou certo que o código é adaptável:
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;
}
});
}
});
Aqui está um exemplo de código python que imprime a soma de todos os números primos abaixo de dois milhões:
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
Este é o mais elegante que eu posso pensar em curto prazo.
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;
}
Hope isso ajuda a dar-lhe uma idéia. Tenho certeza que isso pode ser otimizado, no entanto, deve dar-lhe uma idéia de como a sua versão poderia ser mais elegante.
EDIT: Como observado nos comentários deste algoritmo de fato retorna valores errados para numberToGenerate <2. Eu só quero salientar, que eu não estava tentando postar-lo um ótimo método para gerar nobre números (veja-se a resposta de Henri para isso), eu estava mearly apontando como seu método poderia ser mais elegante.
Usando programação baseada em fluxo na Funcional Java, eu vim com o seguinte. O tipo Natural é essencialmente um 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()));
Agora você tem um valor, que você pode levar em torno, que é um fluxo infinito de primos. Você pode fazer coisas como esta:
// 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));
Uma explicação da peneira:
- Suponha que o primeiro número no fluxo argumento é primo e colocá-lo na frente da corrente de retorno. O resto da corrente de retorno é um cálculo a ser produzido apenas quando solicitado.
- Se alguém pede para o resto do fluxo, peneira chamada no resto do fluxo de argumento, filtrando os números divisíveis pelo primeiro número (o restante da divisão é zero).
Você precisa ter as seguintes importações:
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;
Eu, pessoalmente, acho que isso é uma pequena e limpa (Java) implementação bastante:
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;
}
Tente esta consulta LINQ, ele gera números primos como o esperado
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("");
O método mais simples é a de tentativa e erro: você tentar se qualquer número entre 2 e n-1 divide o seu candidato n
.
Primeiros atalhos são, naturalmente, a) você só tem que verificar os números ímpares, e b) só hav para verificar se há divisores de até sqrt (n).
No seu caso, onde você gerar todos os números primos anteriores no processo, bem como, você só tem que verificar se algum dos números primos em sua lista, até sqrt (n), divide n.
Deve ser o mais rápido você pode obter para o seu dinheiro: -)
Editar
Ok, código, você me pediu isso. Mas estou avisando :-), este é 5-minutos-rápidas e suja de código 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;
Para saber primeiros 100 números primos, seguir código java pode ser considerado.
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);
Eu tenho isso por primeira leitura do "Crivo de Atkin" na Wikki mais algum pensamento antes que dei a isso - eu gastar muito tempo de codificação do zero e ficar completamente zerada em pessoas sendo crítico do meu compilador-like, muito denso estilo de codificação + Eu nem sequer feito uma primeira tentativa para executar o código ... muitos dos paradigma que eu aprendi a utilização está aqui, basta ler e chorar, começa o que você puder.
Tenha absoluta e totalmente certo para realmente testar tudo isso antes de qualquer utilização, com certeza não mostrar a ninguém - é para a leitura e considerando as idéias. Preciso ferramenta primality trabalhando de modo que este é o lugar onde eu começo cada vez que eu tenho que obter algo de trabalho.
Obter uma compilação limpa, em seguida, começar a tirar o que é defeituoso - Eu tenho quase 108 milhões combinações de teclas de código utilizável fazê-lo desta forma, ... Use o que você pode.
Eu vou trabalhar na minha versão amanhã.
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
Tente este código.
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();
}
Aqui está o código 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>
Resultados: 10000 Números Primos em menos de um segundo
100000 Números Primos em 63 segundos
Captura de tela de 100 primeiros números primos
