소수를 찾는 것은 프로그래밍의 전례이며, 종종 누군가가 처음 시도하는 심각한 프로그램입니다 (보통 시험 분할).
그러나 소수는 이미 마모되었습니다. 다음으로 더 흥미로운 것은 소수의 격차를 얻는 것입니다 : 연속적인 소수 사이의 가장 긴 간격. 이들은 매우 희귀하고 “귀중한”것입니다. 처음 몇 쌍과 그 차이점은 다음과 같습니다.
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
...
아버지는 10K까지의 재미를 위해 이것을 손으로 계산했습니다. 코드가 얼마나 짧은 지 보자.
규칙 :
- 프라임 테스트, 프라임 생성 또는 프라임 갭을위한 내장 함수 없음
- http://oeis.org/A002386 또는 이와 유사한 정보를 검색하지 않음 (원격에서 사기꾼 냄새를 맡을 수 있습니다 :))
- 사전 계산 된 배열이 없음
- 내부 정수 유형이 실패 할 때까지 계속 인쇄
캐릭터 수가 가장 적습니다. 소수없이 공백 만 인쇄하는 경우 +10 자
내장 함수가있는 버전을 흥미로울 수도 있습니다. 창의력을 발휘하십시오.
설명 : 소수를 살펴보고 이전에 본 격차보다 큰 격차를 볼 때마다보고합니다. 예를 들어, 3에서 5 사이의 너비는 2 단위입니다. 5와 7 사이의 격차도 2이지만 오래된 뉴스입니다. 더 이상 걱정하지 않습니다. 새로운 가장 큰 차이가있을 때만보고합니다. 이것은 격차가 넓어지고 넓어짐에 따라 소수가 점점 줄어들고 있음을 반영합니다.
편집 : 대부분의 답변은 훌륭하고 더 많은 인정을받을 가치가 있습니다. 그러나 지금까지 48 자로 된 GolfScript 항목이 가장 짧습니다.
답변
GolfScript 66 59 57 49 48
[2.0{:d{;\;.{).{(1$1$%}do(}do.2$-.d>!}do].p~.}do
여기에서 http://golfscript.apphb.com/을 실행하는 데 문제가 있지만 (사이트는 무한 루프를 좋아하지 않습니까?) golfscript.rb를 사용하여 컴퓨터에서 실행할 때 제대로 작동합니다. 저는 GolfScript를 처음 사용하므로 골프를 더 많이 할 수 있습니다. 업데이트 : 알고리즘을 변경하지 않고도 이것이 훨씬 더 많이 줄어들 수 있다고 생각하지 않습니다.
처음 몇 줄이 인쇄됩니다 ( “”인쇄가 마음에 들지 않으면 스크립트의 시작 부분에 추가 할 수 있지만 최대 49 자까지 가능합니다) :
[2 3 1]
["" 3 5 2]
["" 7 11 4]
["" 23 29 6]
["" 89 97 8]
["" 113 127 14]
["" 523 541 18]
["" 887 907 20]
["" 1129 1151 22]
...
이것이 어떻게 작동하는지에 대한 일반적인 사람이 읽을 수있는 아이디어 (이 버전에서는 스택을 사용하지 않기 때문에 약간 다릅니다) :
cur_prime = 2
next_prime = 2
gap = 0
do {
do {
cur_prime = next_prime
do {
next_prime = next_prime + 1
possible_factor = next_prime
do {
possible_factor = possible_factor - 1
} while (next_prime % possible_factor > 0)
} while (possible_factor != 1)
} while (next_prime - cur_prime <= gap)
gap = next_prime - cur_prime
print [cur_prime next_prime gap]
} while (true)
답변
파이썬 121 개 110 109 108 104 103 문자
p,n,m=[2],3,0
while 1:
if all(n%x for x in p):
c=n-p[0]
if m<c:m=c;print(p[0],n,c)
p=[n]+p
n+=1
처음 여기에 대답하려고했을 때, 나는 그것을 올바르게했으면 좋겠다.
흠, 파이썬 2.x로 다운 그레이드하여 인쇄물에 다른 문자를 저장할 수 있습니다 …
답변
자바 스크립트, 90 85 78 74 자
짧은 코드
(Google Closure Compiler-고급 최적화, 일부 수동 편집, @ MT0 추가 편집 )
for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b)
긴 코드
var lastPrime = 2,
curNumber = lastPrime,
maxDistance = 0,
i;
// check all numbers
while( curNumber++ ) {
// check for primes
i = curNumber;
while( curNumber % --i != 0 ) {}
// if prime, then i should be equal to one here
if( i == 1 ) {
// calc distance
i=curNumber-lastPrime;
// new hit
if( maxDistance < i ) {
maxDistance = i;
console.log( lastPrime, curNumber, maxDistance );
}
// remember prime
lastPrime = curNumber;
}
}
산출
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
...
소수에 대해서는 매우 비효율적 인 테스트이지만 더 적은 문자를 사용합니다.
여기에 첫 번째 게시물이므로 실수를 용서하십시오.
답변
매스 매 티카, 114 108
시퀀스의 특정 지점이 지나면 팬이 회전하고 CPU가 프리셀을 재생하는 동안 바쁘게 보이도록 최선을 다하고 있음을 의심하기 시작하지만 무한 출력을 허용합니다.
p@x_:=NestWhile[#+1&,x+1,Divisors@#≠{1,#}&];m=0;q=1;While[1<2,If[p@q-q>m,Print@{q,p@q,p@q-q};m=p@q-q];q=p@q]출력 샘플 (이것은 처음 ~ 30 초에 픽업 된 샘플입니다) :
{1,2,1}
{3,5,2}
{7,11,4}
{23,29,6}
{89,97,8}
{113,127,14}
{523,541,18}
{887,907,20}
{1129,1151,22}
{1327,1361,34}
{9551,9587,36}
{15683,15727,44}
{19609,19661,52}
{31397,31469,72}
{155921,156007,86}
{360653,360749,96}
{370261,370373,112}
{492113,492227,114}
{1349533,1349651,118}
{1357201,1357333,132}
{2010733,2010881,148}
Ungolfed 코드 :
p@x_ := NestWhile[
# + 1 &,
x + 1,
Divisors@# ≠ {1, #} &];
m = 0;
q = 1;
While[
1 < 2,
If[
p@q - q > m,
Print@{q, p@q, p@q - q}; m = p@q - q];
q = p@q]답변
하스켈 – 122 116 114 112 110
q=[n|n<-[3..],all((>0).rem n)[2..n-1]]
d m((p,q):b)|q-p>m=print(p,q,q-p)>>d(q-p)b|q>p=d m b
main=d 0$zip(2:q)q
Will Ness 에서 도난당한 (비효율적 인) 프라임리스트 표현 .
-편집-나는 x|y=z|w=q유효한지 몰랐다 .
답변
MATLAB 104 89
가능한 모든 부서를 확인하여 기본 방법을 구현했습니다.
a=2;g=0;for n=3:inf;b=n*(sum(mod(n,1:n)<1)<3);h=b-a;if(h>g)g=h;[a,b,h]
end;a=max(a,b);end
산출:
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20