소수를 생성하는 가장 우아한 방법
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 구현 또는 해당 문제에 대한 다른 유사한 언어(하스켈은 아님)에 만족합니다).
저는 이 함수를 작성하는 방법을 알고 있지만 어젯밤에 작성했을 때 기대했던 것만큼 좋은 결과를 얻지 못했습니다.내가 생각해낸 내용은 다음과 같습니다.
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)
- 에라토스테네스 체(starblue)의 매우 깔끔한 구현
- 자바를 사용하세요
BigInteger모래nextProbablePrime매우 간단한 코드의 경우 특별히 효율적이라고는 상상할 수 없지만(dfa) - LINQ를 사용하여 소수 목록 생성(Maghis)
- 텍스트 파일에 소수를 많이 넣고 필요할 때 읽어옵니다(darin)
편집 2:나는 C#으로 구현 여기에 제공된 몇 가지 방법과 여기에 언급되지 않은 또 다른 방법이 있습니다.모두가 먼저 찾아요 N 효과적으로 소수화됩니다(그리고 나는 괜찮은 방법 체에 제공할 한계를 찾는 것).
해결책 2
도움이되는 답변을 한 모든 분들께 감사드립니다. 다음은 첫 번째를 찾는 몇 가지 다른 방법의 구현입니다. N C#의 프라임. 처음 두 가지 방법은 여기에 게시 된 내용입니다. (포스터 이름은 제목 옆에 있습니다.) 언젠가 Atkin의 체를 할 계획이지만, 현재 여기의 방법만큼 간단하지는 않습니다. 누구 든지이 방법을 개선하는 방법을 볼 수 있다면 다음과 같이 알고 싶습니다 :-)
표준 방법 (피터 스미트, 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;
}
Sundaram의 체
나는 만 발견했다 이 체 최근에도 간단하게 구현할 수 있습니다. 내 구현은 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;
}
다른 팁
견적을 사용하십시오
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;
}
낡은 질문을 다시 부과하지만 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;
}
당신은 살펴 봐야합니다 가능한 프라임. 특히 살펴보십시오 무작위 알고리즘 그리고 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;
}
실제로 여기에는 더 좋은 서식이있는 일부 게시물의 변형입니다.
나는 당신이 비 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#:
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
}
CC-By-SA 라이센스에 따른 St.Wittum 13189 Berlin Germany의 Copyrights 2009https://creativecommons.org/licenses/by-sa/3.0/
모든 프라임을 계산하는 단순하지만 가장 우아한 방법은 이것 일 것입니다. 그러나이 방법은 느리게 진행되며 교수진 (!) 기능을 사용하기 때문에 메모리 비용이 훨씬 높습니다. 파이썬에서 구현 된 알고리즘에 의해 모든 프라임을 생성합니다
#!/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);
}
일부 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에서 그것을 수행했지만 라이브러리는 열거와 동일한 개념을 사용하기 때문에 코드가 적응할 수 있다고 확신합니다.
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;
}
이것이 당신에게 아이디어를주는 데 도움이되기를 바랍니다. 나는 이것이 최적화 될 수 있다고 확신하지만, 버전이 어떻게 더 우아하게 만들 수 있는지 아이디어를 제공해야합니다.
편집하다: 의견에 언급 된 바와 같이,이 알고리즘은 실제로 Numbertengate <2에 대한 잘못된 값을 반환합니다. 나는 그에게 소수를 생성하는 훌륭한 방법을 게시하려고하지 않았다는 것을 지적하고 싶습니다 (Henri의 대답을보십시오). 그의 방법이 어떻게 더 우아하게 만들 수 있는지를 지적합니다.
스트림 기반 프로그래밍 사용 기능적 자바, 나는 다음을 생각해 냈습니다.유형 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) Dividers를 SQRT (N)까지 확인하는 것만 있습니다.
프로세스에서 이전의 모든 프라임을 생성하는 경우에도 SQRT (N)까지 목록에있는 프라임이 n을 나누는 지 확인하면됩니다.
돈을 위해 얻을 수있는 가장 빠른 것이어야합니다 :-)
편집하다
좋아요, 코드, 당신은 그것을 요청했습니다. 그러나 나는 당신에게 경고합니다 :-), 이것은 5 분짜리 Quick and 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);
나는 Wikki에서 "Atkin의 Sieve Of Atkin"을 처음 읽음으로써 이것을 처음 읽었습니다. 나는 이것에 대해 주신 사전 생각 - 나는 처음부터 코딩하는 데 많은 시간을 소비하고 내 컴파일러와 같은 매우 밀집된 코딩에 비판적인 사람들에게 완전히 제로를 얻습니다. 스타일 + 코드를 실행하려는 첫 번째 시도조차하지 않았습니다 ... 내가 사용하는 법을 배운 많은 패러다임이 여기에 있습니다.
어떤 용도로 도이 모든 것을 실제로 테스트해야합니다. 확실히 누구에게도 보여주지 마십시오. 아이디어를 읽고 고려하기위한 것입니다. 원시 도구를 작동시켜야합니다. 그래서 이것은 무언가가 작동해야 할 때마다 시작하는 곳입니다.
하나의 깨끗한 컴파일을 얻은 다음 결함이있는 것을 제거하기 시작하십시오.이 방법으로 사용 가능한 코드의 거의 1 억 1 천만 키 스트로크가 있습니다.
내일 내 버전에서 작업하겠습니다.
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 초 만에 10 만 소수
처음 100 소수의 스크린 샷
