Szatani-Pierwsi

kim oni są?
są Primeszawierające 666
to Szatan-Najwyżsi: [46663,266677,666599,666683,616669]
to NIE :[462667,665669,36363631,555]

Wątek

Każda liczba większa niż 6661 ma za sobą Szatana-Najwyższych

Wyzwanie

Podano liczbę całkowitą n>6661 znajdź Najwyższego Szatana za (lub równym) i najbliżej siebie.

Przykłady

Integer n=30000ma 3 szatan liczb pierwszych (SP) za nim: [6661, 16661, 26669].
Twój kod musi zostać zwrócony26669 co jest najbliżej niego

Przypadki testowe

Wejście-> Wyjście

6662->6661    
10000->6661    
66697->66697 (a SP returns himself)  
328765->326663  
678987->676661
969696->966677

Zasady

Twój kod powinien działać dla każdego nTwój w Twoim języku.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach!

Mathematica, 82 bajty

Last@Select[Prime@Range@PrimePi@#,!FreeQ[Subsequences[IntegerDigits@#],{6,6,6}]&]&

Neim , 9 bajtów

>ͻ:D+6S𝕚÷

Wyjaśnienie:

>         Increment input
 ͻ        Start infinite loop
  :        Previous prime
   D       Duplicate
    +6     Push 666
      S    Swap
       𝕚   See if 666 is a substring of the top of the stack
        ÷  If true, break

Wypróbuj online!

Galaretka , 10 9 bajtów

Zaoszczędź 10% dzięki @Dennis!

ÆRwÐf666Ṫ

Wypróbuj online!

Wyjaśnienie

ÆR          # All primes in range [2, input]
   Ðf      # Keep those which satisfy
  w        # truthy if y is in x
     666   #           ^ (this is y)
        Ṫ  # Tail (take the last element)

Pyt , 15 14 bajtów

Zapisano 1 bajt z pomocą Dave'a .

Błędy pamięci dla 969696 i cokolwiek wyższego na moim komputerze, ale dobrze jest, jeśli ma wystarczającą ilość pamięci.

ef&/`T*3\6P_TS

Wypróbuj tutaj lub sprawdź pakiet testowy.

W jaki sposób?

ef & / `T * 3 \ 6P_TSQ - Pełny program, z niejawnym wejściem (Q) na końcu

             SQ - Zakres [1, Q]
 f - Filtruj.
          P_T - Czy liczba pierwsza?
  & - I
   / `T * 3 \ 6 - Zawiera 666.
e - ostatni element.
                - Wyjmij wynik niejawnie.

Pyth , 14 bajtów

ef/`T*\63fP_TS

Wypróbuj tutaj!

05AB1E , 11 bajtów

ƒNpN666å*iN

Wypróbuj online!

Bash + Core Utils, 51 49 bajtów

seq $1|tac|factor|awk 'NF==2&&/666/&&!a--&&$0=$2'

Bierze argument z wiersza poleceń. Może być dość wolny przy większych liczbach.

Mathematica, 64 62 61 53 bajtów

#//.i_/;!PrimeQ@i||ToString@i~StringFreeQ~"666":>i-1&

-1 bajt dzięki @KellyLowder

-8 bajtów (wow) dzięki @Notatree

Wyjaśnienie

Weź udział. Zmniejszamy to na następujących warunkach:

• wejście nie jest liczbą pierwszą LUB

• cyfry danych wejściowych nie zawierają trzech 6s z rzędu.

Powtarzamy to aż do osiągnięcia szatana.

Perl 5 , 47 bajtów

46 bajtów kodu + 1 dla -p

{$f=0|sqrt;1while$_%$f--;/666/*!$f||$_--*redo}

Wypróbuj online!

Japt , 14 bajtów

õ fj w æ_sø666

Sprawdź to

Skoro nie było Bonus 50% czasu na bazie: sprawdzian finalizuje 969696się pod pół sekundy.

Wyjaśnienie

Domniemane wprowadzenie liczby całkowitej U.

õ

Wygeneruj tablicę liczb całkowitych od 1do U.

fj

Filtruj ( f) liczby pierwsze.

w

Rewers.

æ_

Zwraca pierwszy element, który zwraca prawdziwą wartość (w tym przypadku 1) po przejściu przez funkcję, która sprawdza, czy ...

sø666

Liczba całkowita przekonwertowana na string ( s) zawiera ( ø) 666.

Szybsza alternatywa, 15 bajtów

Ponownie, biorąc pod uwagę, że pierwotnie istniała premia uzależniona od czasu, oto alternatywne i znacznie szybsze rozwiązanie, którego nie mogę dalej grać w golfa.

U-@j *U´sø666}a

Sprawdź to

PowerShell , 128 bajtów

param($n)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}for(){if($n-match666-and($n-eq(f $n))){$n;exit}$n--}

Wypróbuj online!

Program PowerShell nie ma żadnych wbudowanych głównych faktoryzacji, więc pożycza kod z mojej odpowiedzi na temat znajomych Prime Factors .

Bierzemy dane wejściowe $n, a następnie deklarujemy nowy, function fktóry oblicza czynniki wejściowe $a. Jeśli dane wejściowe $asą liczbą pierwszą, to właśnie zwróci $a.

Główną częścią programu jest nieskończona for()pętla. Wewnątrz pętli sprawdzamy, czy $n -matches jest 666i czy $njest liczbą pierwszą (tzn. Czy $npasuje do wszystkich czynników $n). Jeśli tak, to umieszczamy $ngo w potoku i exit, z niejawnym wynikiem. W przeciwnym razie zmniejszamy $n--i kontynuujemy pętlę.

Python 2, 77 76 bytes

Edit: -1 byte thanks to @Mr.Xcoder

Slow running time, runs in O(n^2)

lambda x:max(q for q in range(x+1)if"666"in`q`*all(q%t for t in range(2,q)))

Try it online!

Another 76 bytes solution

lambda x:max(q*("666"in`q`*all(q%t for t in range(2,q)))for q in range(x+1))

Try it online!

With SymPy 73 bytes

lambda x:max(q for q in primerange(0,x+1)if"666"in`q`)
from sympy import*

Try it online!

PowerShell, 71 69 64 bytes

param($s)for(;$s-notmatch666-or(2..($s/2)|?{!($s%$_)});$s--){}$s

Try it online!

• 328765 takes ~30 seconds on my machine, but times out the 60 second limit on Tio.run.

• 678987 takes ~1.5 minutes.

• 969696 takes ~4.5 minutes.

MATL, 16 bytes

ZqP"@V'666'Xf?@.

Try it at MATL Online

Explanation

         Implicitly grab input (n)
Zq       Compute the primes up to n (output is in increasing order)
P        Flip the array (so larger primes come first)
"        For each prime
  @V     Convert it to a string
  '666'  Push the string literal '666' to the stack
  Xf     Find the location of '666' in the prime
  ?      If it was present...
    @.   Push it to the stack and break
         Implicitly display the stack contents

C++ 389 bytes

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;typedef boost::multiprecision::cpp_int Z;int main(int,char**v){mt19937 m(clock());independent_bits_engine<mt11213b,256,Z>g(m);Z n{v[1]},p;while(p++<=n)if(miller_rabin_test(p,25,g)&&p.convert_to<std::string>().find( "666" )!=-1)std::cout<<p<<" ";}

This is a full program!
You'll need Boost to compile it. (Or copy and paste into your favorite online C++ shell.)
Run it from the command-line giving n as argument.

Ungolfed:

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;

typedef boost::multiprecision::cpp_int integer;

int main( int argc, char** argv )
{
  mt19937 mt( clock() );
  independent_bits_engine <mt11213b, 256, integer> rng( mt );

  integer input {argv[ 1 ]};
  integer possible;

  while (possible++ <= input)
    if (
      // is_prime( possible )
      miller_rabin_test( possible, 25, rng )
    && 
      // possible has "666" in it
      (possible.convert_to <std::string> ().find( "666" ) != std::string::npos))

    std::cout << possible << " ";
}

Shortcuts were made in terms of random number testing. The original code started testing possible primes at 6661 and incremented by two. You'll also get a compiler warning because of that (-1) there instead of npos.

Still, this runs pretty quickly. It only took about 40 seconds to find all 214 satan primes under 1,000,000 on my old AMD Sempron 130.

:^D

Bash + bsd-games package, 33

• 2 bytes saved thanks to @FedericoPoloni.

primes 2 $[$1+1]|grep 666|tail -1

Try it online.

Python 3, 85 83 80 bytes

Halvard's is 4 bytes shorter because it's done in Python 2.

lambda k:max(x for x in range(k+1)if"666"in str(x)*all(x%i for i in range(2,x)))

Try it online!

Give it some time, it's extremely slow because of its O(n^2) complexity.

JavaScript (ES6), 55 54 bytes

-1 byte thanks to @ThePirateBay.

f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)

Very slow with large inputs. Primality test adapted from this code golf answer.

Timings

• Input 10000 took 10 seconds
• Input 328765 took 3 minutes
• Input 678987 took 9 minutes
• Input 969696 took 16 minutes

Tests

Some of these will hang your browser for several minutes.

f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)

function test(n) {
  O.value="Working..."
  setTimeout(_=>{
    let t = Date.now()
    O.value=`f(${n}) = ${f(n)} in ${(Date.now()-t)/1000}s`
  }, 10)
}

Tests<br>
<button onclick="test(6662)">6662</button>
<button onclick="test(10000)">10000</button>
<button onclick="test(328765)">328765</button>
<button onclick="test(678987)">678987</button>
<button onclick="test(969696)">6662</button><br>
Result<br>
<input id=O type=text size=25 readonly>

Faster Version, 56 bytes

Completes each test case in under a second.

f=n=>/666/.test(n)&&eval("for(d=2;n%d++;);d>n")?n:f(n-1)

;[6662, 10000, 328765, 678987, 969696].forEach(n=>console.log(`f(${n}) -> ${f(n)}`))

Ruby, 67, 66, 58, 56 bytes

Includes +7 bytes for -rprime

->z{z.downto(1).find{|x|/666/=~x.to_s&&x.prime?}}

It's pretty fast, computing values up to ~2^52 in about a second and 2^64 in under 5 minutes (2011 MBP, Ruby 2.3.1).

Stax, 10 bytes

ü>:Ñb/VP6─

Run and debug it

Explanation (unpacked):

^w:pc$666$#! Full program, implicit input-parsing
^            Increment input
 w           do-while:
  :p           Previous prime
    c$         Copy and stringify
      666$     Push "666"
          #    Number of occurences
           !   Logical not
             Implicit output

PHP, 148 bytes

<?php $p=[2];$s=[];for($i=3;$i<=$argv[1];$i++){foreach($p as $q)if($i%$q===0)continue 2;$p[]=$i;if(strpos($i,'666')!==false)$s[]=$i;}echo end($s);?>

Try it online!

Perl 6, 35 bytes

my&f={/666/&&.is-prime??$_!!f $_-1}

Try it online!

Straightforward recursive solution.

C# (.NET Core), 117 115 112 bytes

f=>{for(int i=f;i>1;i--){int p=1,j=2;while(j<i)if(i%j++<1)p=0;if(p>0&$"{i}".Contains("666"))return i;}return 0;}

Try it online!

• 2 bytes saved by removing unnecessary braces.
• 3 bytes saved by combining int declarations.

I'm sure this could be made shorter; maybe by recursively calling func f and removing the outer for-loop.

Recursive Approach, 85 bytes

i=>{int p=1,j=2;while(j<i)if(i%j++<1)p=0;return p>0&$"{i}".Contains("666")?i:f(--i);}

Try it online!

I'm unsure how well this approach fits within the bounds of code-golf due to having to set the Func<int,int> f = null first, and that f is called again, but not counted towards the bytes. Any clarification would be appreciated.