Выведите ближайшие простые числа

9

Напишите программу, которая принимает входные данные (которые могут быть или не быть простыми), и перечисляет непосредственное простое число, следующее за ним и предшествующее ему.

Пример ввода:

1259

Пример вывода:

1249 1277

Кратчайшая программа выигрывает. Необходимо выполнить в течение 10 секунд на современном настольном ПК. Входы будут ограничены до 10 000 максимум.

code-golf number primes Томас О
источник
2
Кажется несколько странным перечислять ограничение по времени, не ограничивая при этом диапазон возможных входных данных. Должны ли мы найти простые числа в несколько тысяч цифр в течение десяти секунд?
Анон.
@Anon. Предположим, я не буду смешно вводить данные, но программа должна быть несколько оптимизирована. Я уточнил текст вопроса.
Томас О
моя однострочность не оптимальна, но она работает за ~ 1 с при вводе 10000. Вы должны очень стараться, чтобы получить 10 с.
ниндзя
@ninjalj Просто чтобы отсеять абсолютно ужасные алгоритмы.
Томас О
3
так что вы не рассматриваете проверку числа nна простоту, создавая nдлинные строковые символы и проверяя их на соответствие регулярному выражению, абсолютно ужасно?
ниндзя

Ответы:

6

Perl 5.10 (perl -E), 65 символов

Половина кредита (по крайней мере) должна идти в @J B.

$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}
ninjalj
источник
отлично! главное тестовое выражение!
Мин-Тан
да, я узнал об этом на stackoverflow.com/questions/3543811/code-golf-happy-primes
ninjalj
Похоже, вы могли бы сохранить пару символов с помощью регулярного выражения в кавычках (+2 для qr, -4 для того , чтобы не нуждаться в разделителях позже).
Анон.
На самом деле, это работает без qr. LMGTFY: 81 символ$m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"
JB
Второй раунд, учитывающий оба совпадения (66 символов):perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}'
JB
12

Математика , 19

#~NextPrime~{-1,1}&
Mr.Wizard
источник
очень умный: 0)
доктор Велизарий
10

Mathematica: 28 символов

(k=NextPrime;{k[#,-1],k@#})&

Применение

%[1259]
{1249, 1277}  

%[121231313159]  
{121231313129, 121231313191}
Доктор Велизарий
источник
3

Питон - 93

Основано на ответе fR0DDY . Я в основном слил строки 4 и 5 и сократил строку 2, используя другой метод.

n=input()-1
m=n+2
f=lambda n:any(n%x<1for x in range(2,n))
exec"n-=f(n);m+=f(m);"*m
print n,m
JPvdMerwe
источник
2

Python 116 111 109 символов 

n=input()-1
m=n+2
f=lambda n:any(pow(b,n-1,n)>1for b in(3,5,7,13))
while f(n):n-=1
while f(m):m+=1
print n,m
fR0DDY
источник
1
использоватьf=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))
st0le
@ fR0DDY, вместо использования первых 3 строк n=input()-1и m=n+2, сохраняет 3 символа ... я думаю.
st0le
и, возможно, вы можете заменить not(all(...)), any(...)изменив логическое значение
st0le
Вы не считаете новые строки. Фактический счет есть 108.
JPvdMerwe
1
Также, пожалуйста, посчитайте новые строки в вашем персонаже. -1 для обмана других.
Мойнудин
1

Haskell: 99

s(z:y)=z:s[x|x<-y,mod x z>0];f(x:y:z:w)=(x,z):f(y:z:w);p x=(head.filter(\(c,v)->c<x&&v>x).f.s)[2..]

пример

Main> p 1259
(1249,1277)
Мин-Tang
источник
1

Python, 116 139 символов (двойной отступ - tab-char)

Использует хорошее оле Сито Эратосфена

Редактирует и (спасибо TON @JPvdMerwe). Должен работать с простыми числами сейчас.

l=n=input();a=range(n*2)
for i in a[2:]:a=[k for k in a if k==i or k%i]
for g in a:
 if g>n:print l,g;break
 if i!=n:l=g

оригинал

a=range(9999)
j=lambda a,n:[i for i in a if i==n or i%n]
for i in a[2:]:a=j(a,i)
o=n=input();
for i in a:
 if o<n and i>n: 
  print o,i
 o=i
Дуг Т.
источник
-1 За не считая НЕОБХОДИМЫХ пропусков .
JPvdMerwe
@JPvdMerwe Моя ошибка, я новичок здесь, и я понял, что, возможно, использовал неправильный показатель из моего редактора.
Дуг Т.
@JPvDMerwe также спасибо за помощь в редактировании
Дуг Т.
@DougT круто все ошибаются :) +1 Чтобы отменить мой отрицательный голос, просто убедитесь в следующий раз.
JPvdMerwe
Один трюк, который вы можете сделать, это переместить строки 1-3 ниже строки 4 и заменить a=range(9999)на a=range(n). Также в строке 2 вам не нужно переходить aк лямбде, вы можете просто использовать ее. Это должно сильно сбрить.
JPvdMerwe
1

Scala 119:

def p(n:Int)=(2 to n-1).exists(n%_==0)
def i(n:Int,v:Int):Int=if(!p(n+v))n+v else i(n+v,v)
Seq(-1,1).map(i(readInt,_))

ungolfed:

def notPrime (n:Int) = 
    (2 to n-1).exists (n % _ == 0)

def itPrime (n: Int, vector:Int) : Int =
    if (! notPrime (n+vector)) n+vector
    else itPrime (n+vector, vector)

def nearbyPrime (value: Int) =
    Seq (-1, 1).map (sign => itPrime (value, sign))

21.2s для запуска всех 9998 целых с 3 до 10.000

Пользователь неизвестен
источник
1

Swift 190 187 185 110

Свифт очень плох в код-гольфе, но я все равно попробовал: D
Он становится короче и короче ... (Спасибо @HermanLauenstein за удаление 75 байт)

var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}
Йозеф Золлер
источник
-75 байт с большой реструктуризацией var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}(я еще не проверил это должным образом)
Herman L
Спасибо @HermanLauenstein. Это мой первый код-гольф, поэтому мне может понадобиться любая помощь :)
Йозеф Золлер,
0

Python (123)

import Primes as p
j=i=int(input())
n=p.primes(i*2)
while not i in n[:]:
 i+=1
print(i)
while not j in n[:]:
 j-=1
print(j)

ПРИМЕЧАНИЕ: Primesмодуль был написан мной, но он существовал до того, как был задан этот вопрос. Это НЕ было написано для этого. Тем не менее, это было сочтено несправедливым, поэтому вот обновленная версия.

Python (215)

j=i=int(input())
import math as m
s=list(range(i*2))
for n in s[:]:
 for l in range(1,int(m.ceil(m.sqrt(n)))):
  if(n%l)==0and l!=1and n in s:s.remove(n)
while not i in s:i+=1
print(i)
while not j in s:j-=1
print(j)
Джон
источник
Я не знаю, как вам удалось ошибиться, но это на самом деле:123
JPvdMerwe
Кроме того, @John, если модуль теперь не является частью языка, в интересах справедливости вы должны включить код. Но слава на честность.
JPvdMerwe
Я думаю, что это обман, чтобы использовать Primes; против духа кода гольф.
Томас О,
@JPv: Да. Это было неправильно. Интересно, как это случилось.
Джон
@Thomas, @JPv: я разместил обновленную версию без импорта.
Джон
0

C (gcc) , 98 байт

p(n,i){for(i=2;i<n;)n=n%i++?n:0;i=n;}g(n,d){for(;!p(n+=d););printf("%d ",n);}f(n){g(n,-1);g(n,1);}

Попробуйте онлайн!

Полная версия программы, C (gcc) , 116 байт

p(n,i){for(i=2;i<n;)n=n%i++?n:0;i=n;}g(n,d){for(;!p(n+=d););printf("%d ",n);}main(n){scanf("%d",&n);g(n,-1);g(n,1);}

Попробуйте онлайн!

Обе версии предполагают, что мы никогда не проверяем 1 на простоту, что происходит только в том случае, если входное значение равно 2 или ниже, и в этом случае выходное значение в любом случае будет неопределенным.

gastropner
источник