소수를 생성하는 가장 우아한 방법 [닫힌]
이 기능을 구현하는 가장 우아한 방법은 무엇입니까?
ArrayList generatePrimes(int n)
이 함수는 첫 번째 n소수 (편집 : where n>1)를 생성하므로 with generatePrimes(5)를 반환합니다 . (저는 C #에서이 작업을 수행하고 있지만 Java 구현 또는 다른 유사한 언어 (하스켈이 아님)에 만족합니다).ArrayList{2, 3, 5, 7, 11}
이 함수를 작성하는 방법을 알고 있지만 어제 밤에 작성했을 때 내가 기대했던 것만 큼 멋지지 않았습니다. 내가 생각해 낸 것은 다음과 같습니다.
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;
}
분명히 비효율적이기를 원하지는 않지만 속도에 대해서는 너무 걱정하지 않습니다. 어떤 방법이 사용되는지 (순진하거나 체 또는 다른 것) 신경 쓰지 않지만, 그것이 어떻게 작동하는지 상당히 짧고 분명하기를 바랍니다.
편집 : 많은 사람들이 내 실제 질문에 대답하지 않았지만 응답 해 주신 모든 분들께 감사드립니다. 다시 말해서, 소수 목록을 생성하는 깔끔한 코드를 원했습니다. 나는 이미 여러 가지 방법을 알고 있지만 명확하지 않은 코드를 작성하는 경향이 있습니다. 이 스레드에서 몇 가지 좋은 옵션이 제안되었습니다.
- 내가 원래 가지고 있었던 것의 더 좋은 버전 (Peter Smit, jmservera 및 Rekreativc)
- Eratosthenes (starblue) 체의 매우 깨끗한 구현
- 특히 효율적이라고 상상할 수는 없지만 (dfa) Java의
BigInteger및nextProbablePrime매우 간단한 코드를 사용하십시오. - LINQ를 사용하여 소수 목록 (Maghis)을 느리게 생성
- 많은 소수를 텍스트 파일에 넣고 필요할 때 읽습니다 (다린).
편집 2 : 여기에 제공된 두 가지 방법과 여기에 언급되지 않은 다른 방법 을 C # 으로 구현했습니다 . 그들은 모두 처음 n 개의 소수를 효과적으로 찾습니다 (그리고 체에 제공 할 한계를 찾는 적절한 방법 이 있습니다).
견적 사용
pi(n) = n / log(n)
n까지 소수의 수에 대해 한계를 찾은 다음 체를 사용하십시오. 추정치는 n까지 소수의 수를 다소 과소 평가하므로 체가 필요한 것보다 약간 더 커집니다. 괜찮습니다.
이것은 내 표준 Java sieve이며 일반 랩톱에서 약 1 초 만에 처음 백만 개의 소수를 계산합니다.
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;
}
도움을 주신 모든 분들께 감사드립니다. 다음은 C #에서 처음 n 개의 소수 를 찾는 몇 가지 다른 방법의 구현입니다 . 처음 두 가지 방법은 여기에 게시 된 것과 거의 같습니다. (포스터 이름은 제목 옆에 있습니다.) 현재의 방법만큼 간단하지는 않지만 Atkin의 체를 만들 계획입니다. 누구든지 이러한 방법을 개선하는 방법을 볼 수 있다면 알고 싶습니다 :-)
표준 방법 ( Peter Smit , jmservera , Rekreativc )
첫 번째 소수는 2입니다. 이것을 소수 목록에 추가합니다. 다음 소수는이 목록에있는 어떤 숫자로도 균등하게 나눌 수없는 다음 숫자입니다.
public static List<int> GeneratePrimesNaive(int n)
{
List<int> primes = new List<int>();
primes.Add(2);
int nextPrime = 3;
while (primes.Count < n)
{
int sqrt = (int)Math.Sqrt(nextPrime);
bool isPrime = true;
for (int i = 0; (int)primes[i] <= sqrt; i++)
{
if (nextPrime % primes[i] == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
primes.Add(nextPrime);
}
nextPrime += 2;
}
return primes;
}
이것은 테스트되는 숫자의 제곱근까지 나눌 수 있는지 테스트함으로써 최적화되었습니다. 홀수 만 테스트합니다. 이는 상기 형태의 숫자를 테스트함으로써 최적화 될 수있다 6k+[1, 5]거나 30k+[1, 7, 11, 13, 17, 19, 23, 29]또는 등등 .
에라토스테네스의 체 ( starblue )
이것은 k에 대한 모든 소수를 찾습니다 . 처음 n 개의 소수 의 목록을 만들려면 먼저 n 번째 소수의 값을 근사해야합니다 . 여기 에 설명 된대로 다음 방법 이이를 수행합니다.
public static int ApproximateNthPrime(int nn)
{
double n = (double)nn;
double p;
if (nn >= 7022)
{
p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
}
else if (nn >= 6)
{
p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
}
else if (nn > 0)
{
p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
}
else
{
p = 0;
}
return (int)p;
}
// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
BitArray bits = new BitArray(limit + 1, true);
bits[0] = false;
bits[1] = false;
for (int i = 0; i * i <= limit; i++)
{
if (bits[i])
{
for (int j = i * i; j <= limit; j += i)
{
bits[j] = false;
}
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfEratosthenes(limit);
List<int> primes = new List<int>();
for (int i = 0, found = 0; i < limit && found < n; i++)
{
if (bits[i])
{
primes.Add(i);
found++;
}
}
return primes;
}
순 다람의 체
최근에 야이 체를 발견 했지만 아주 간단하게 구현할 수 있습니다. 내 구현은 Eratosthenes의 체만큼 빠르지는 않지만 순진한 방법보다 훨씬 빠릅니다.
public static BitArray SieveOfSundaram(int limit)
{
limit /= 2;
BitArray bits = new BitArray(limit + 1, true);
for (int i = 1; 3 * i + 1 < limit; i++)
{
for (int j = 1; i + j + 2 * i * j <= limit; j++)
{
bits[i + j + 2 * i * j] = false;
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfSundaram(limit);
List<int> primes = new List<int>();
primes.Add(2);
for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
{
if (bits[i])
{
primes.Add(2 * i + 1);
found++;
}
}
return primes;
}
오래된 질문을 구제했지만 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); 이 함수는 number = 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;
}
가능한 소수를 살펴 봐야 합니다. 특히 Randomized Algorithms 및 Miller-Rabin 소수성 테스트를 살펴보십시오 .
완전성을 위해 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;
}
실제로 여기에 더 좋은 서식을 적용한 일부 게시물의 변형 일뿐입니다.
Copyrights 2009 by St. Wittum 13189 Berlin GERMANY under CC-BY-SA License https://creativecommons.org/licenses/by-sa/3.0/
모든 PRIMES를 계산하는 간단하지만 가장 우아한 방법은 이것이지만,이 방법은 느리고 교수 (!) 함수를 사용하기 때문에 메모리 비용이 훨씬 더 높지만 응용 프로그램에서 Wilson Theoreme의 변형을 보여줍니다. Python으로 구현 된 알고리즘으로 모든 소수 생성
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
나는 당신이 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;
}
제한이 음수이거나 2보다 작 으면 수표를 생략했습니다 (현재 메서드는 항상 최소 2 개를 소수로 반환합니다). 그러나 그것은 모두 쉽게 고칠 수 있습니다.
최신 정보
다음 두 가지 확장 방법으로
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;
}
덜 효율적이지만 (제곱근이 꽤 자주 재평가되기 때문에) 더 깨끗한 코드입니다. 소수를 느리게 열거하도록 코드를 다시 작성할 수 있지만 이로 인해 코드가 상당히 복잡해집니다.
다음 은 C #에서 Sieve of Eratosthenes 를 구현 한 것입니다 .
IEnumerable<int> GeneratePrimes(int n)
{
var values = new Numbers[n];
values[0] = Numbers.Prime;
values[1] = Numbers.Prime;
for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
{
values[outer] = Numbers.Prime;
for (int inner = outer * 2; inner < values.Length; inner += outer)
values[inner] = Numbers.Composite;
}
for (int i = 2; i < values.Length; i++)
{
if (values[i] == Numbers.Prime)
yield return i;
}
}
int FirstUnset(Numbers[] values, int last)
{
for (int i = last; i < values.Length; i++)
if (values[i] == Numbers.Unset)
return i;
return -1;
}
enum Numbers
{
Unset,
Prime,
Composite
}
동일한 알고리즘을 사용하면 조금 더 짧게 할 수 있습니다.
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);
}
LINQ를 사용하여 C #으로 간단한 Eratosthenes 구현을 작성했습니다.
불행히도 LINQ는 int의 무한 시퀀스를 제공하지 않으므로 int.MaxValue :(
캐시 된 각 프라임에 대해 계산하지 않기 위해 후보 sqrt를 익명 유형으로 캐시해야했습니다 (조금 못 생겼습니다).
후보의 sqrt까지 이전 소수 목록을 사용합니다.
cache.TakeWhile(c => c <= candidate.Sqrt)
2부터 시작하는 모든 Int를 확인하십시오.
.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에서 수행했지만 내 라이브러리는 Enumerations와 동일한 개념을 사용하기 때문에 코드가 적응할 수 있다고 확신합니다.
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;
}
});
}
});
다음은 2 백만 미만의 모든 소수의 합을 출력하는 파이썬 코드 예제입니다.
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에 대해 잘못된 값을 반환합니다. 나는 그에게 소수를 생성하는 훌륭한 방법을 게시하려고하지 않았다는 것을 지적하고 싶습니다 (Henri의 대답을보십시오). 나는 그의 방법이 어떻게 더 우아해질 수 있는지 겨우 지적하고 있었다.
Functional 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를 호출하여 첫 번째 숫자로 나눌 수있는 숫자를 필터링합니다 (나머지 나눗셈은 0 임).
다음 가져 오기가 필요합니다.
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을 나누면 시도합니다.
첫 번째 단축키는 물론 a) 홀수 만 확인하면되고 b) sqrt (n)까지의 구분선 만 확인하면됩니다.
프로세스에서 이전 소수를 모두 생성하는 경우에는 목록에있는 소수 중 sqrt (n)까지 n을 나누는 것이 있는지 확인하기 만하면됩니다.
당신의 돈을 위해 얻을 수있는 가장 빠른 것이어야합니다 :-)
수정
좋아, 코드, 당신이 그것을 요청했습니다. 그러나 나는 당신에게 경고합니다 :-), 이것은 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 개의 소수를 찾으려면 다음 자바 코드를 고려할 수 있습니다.
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);
나는 Wikki에서 "Sieve of Atkin"을 처음 읽었을뿐 아니라 이에 대해 미리 생각해 본 적이 있습니다. 저는 처음부터 코딩하는 데 많은 시간을 할애하고 사람들이 제 컴파일러와 같은 매우 조밀 한 코딩을 비판하는 것을 완전히 제로화합니다. 스타일 + 코드를 실행하려는 첫 번째 시도도하지 않았습니다. 제가 사용하는 방법을 배운 많은 패러다임이 여기에 있습니다. 읽고 울면서 할 수있는 것을 얻으십시오.
이 모든 것을 사용하기 전에 절대적으로 확실하게 테스트하고 누구에게도 보여주지 마십시오. 아이디어를 읽고 고려하기위한 것입니다. 나는 소수 도구가 작동하도록해야한다. 그래서 이것이 내가 무언가를해야 할 때마다 시작하는 곳이다.
깨끗한 컴파일을 한 다음 결함이있는 부분을 제거하기 시작합니다. 저는 거의 1 억 8 백만 번의 사용 가능한 코드 키 입력이 이런 방식으로 수행됩니다.
내일 내 버전 작업을 할 것입니다.
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>
결과 : 1 초 이내에 10000 개의 소수
63 초에 100000 개의 소수
처음 100 개의 소수 스크린 샷 
참고 URL : https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers
'code' 카테고리의 다른 글
| 가변 높이의 CSS 플로팅 Div (0) | 2020.10.05 |
|---|---|
| PIL을 사용하여 RGBA PNG를 RGB로 변환 (0) | 2020.10.05 |
| .gitignore에 # * # glob을 추가 하시겠습니까? (0) | 2020.10.05 |
| Scala에서 커링하는 두 가지 방법; (0) | 2020.10.05 |
| C에서 새 디렉토리 만들기 (0) | 2020.10.05 |