[Question]
  [
# Satan-Primes
who are they?  
they are `Primes` containing `666`  
these are Satan-Primes:`[46663,266677,666599,666683,616669]`  
these are **NOT** :`[462667,665669,36363631,555]`
# Plot
*Every number bigger than 6661 has Satan-Primes behind him*
# The Challenge
Given an integer `n>6661` find the Satan-Prime **behind (or equal) and closest** to itself.
# Examples
Integer `n=30000` has 3 Satan-Primes(SP) behind it:`[6661, 16661, 26669]`.  
Your code must return `26669` which is the closest behind it
# Test Cases
Input->Output
```
6662->6661    
10000->6661    
66697->66697 (a SP returns himself)  
328765->326663  
678987->676661
969696->966677
```
# Rules
Yor code should work for any `n` in the range of your language.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest answer in bytes wins!
  
[Answer]
# [Neim](https://github.com/okx-code/Neim), 9 bytes
```
>Õª:D+6Sùïö√∑
```
Explanation:
```
>         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
```
[Try it online!](https://tio.run/##y0vNzP3/3@7sbisXbbPgD3Onzjq8/f9/MzMzS3MA "Neim ‚Äì Try It Online")
[Answer]
# Mathematica, 82 bytes
```
Last@Select[Prime@Range@PrimePi@#,!FreeQ[Subsequences[IntegerDigits@#],{6,6,6}]&]&
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~10~~ 9 bytes
Saved 10% thanks to @Dennis!
```
√ÜRw√êf666·π™
```
[Try it online!](https://tio.run/##y0rNyan8//9wW1D54QlpZmZmD3eu@m99uF3lUdMabyCO/P8/GihqpGNoAAQ6QKaluY6xkYW5mamOmbmFpYW5jqUZCMYCAA "Jelly ‚Äì Try It Online")
### Explanation
```
√Ü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)
```
[Answer]
# [Pyth](https://pyth.readthedocs.io), ~~15~~ 14 bytes
*Saved 1 byte with help from Dave*.
Memory errors for `969696` and anything higher on my machine, but it is fine if it is given enough memory.
```
ef&/`T*3\6P_TS
```
**[Try it here](https://pyth.herokuapp.com/?code=ef%26%2F%60T%2a3%5C6P_TS&input=10000&test_suite_input=6662%0A10000%0A66697%0A76667%0A328765&debug=0) or check out the [Test Suite.](https://pyth.herokuapp.com/?code=ef%26%2F%60T%2a3%5C6P_TS&input=6662-%3E6661++++%0A10000-%3E6661++++%0A66697-%3E66697+%28a+SP+returns+himself%29++%0A328765-%3E326663++%0A678987-%3E676661%0A969696-%3E966677&test_suite=1&test_suite_input=6662%0A10000%0A66697%0A328765&debug=0)**
---
# How?
```
ef&/`T*3\6P_TSQ - Full program, with implicit input (Q) at the end
             SQ - Range [1,Q]
 f              - Filter.
          P_T   - Is prime?
  &             - And
   /`T*3\6      - It contains 666.
e               - Last element.
                - Implicitly output the result.
```
# [Pyth](https://pyth.readthedocs.io), 14 bytes
```
ef/`T*\63fP_TS
```
**[Try it here!](http://pyth.herokuapp.com/?code=ef%2F%60T%2a%5C63fP_TS&input=10000&debug=0)**
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 11 bytes
```
∆íNpN666√•*iN
```
[Try it online!](https://tio.run/##MzBNTDJM/f//2CS/Aj8zM7PDS7Uy/f7/NzYAAgA "05AB1E ‚Äì Try It Online")
[Answer]
# Bash + Core Utils, 51 49 Bytes
```
seq $1|tac|factor|awk 'NF==2&&/666/&&!a--&&$0=$2'
```
Takes command line argument. Can be quite slow with larger numbers.
[Answer]
# Mathematica, ~~64~~ ~~62~~ ~~61~~ 53 bytes
```
#//.i_/;!PrimeQ@i||ToString@i~StringFreeQ~"666":>i-1&
```
*-1 byte thanks to @KellyLowder*
*-8 bytes (wow) thanks to @Notatree*
## Explanation
Take an input. We decrement it under these conditions:
* the input is not prime, OR
* the digits of the inputs does not contain three 6s in a row.
We repeat that until a Satan prime is reached.
[Answer]
# [Perl 5](https://www.perl.org/), 47 bytes
46 bytes of code + 1 for `-p`
```
{$f=0|sqrt;1while$_%$f--;/666/*!$f||$_--*redo}
```
[Try it online!](https://tio.run/##K0gtyjH9/79aJc3WoKa4sKjE2rA8IzMnVSVeVSVNV9da38zMTF9LUSWtpkYlXldXqyg1Jb/2/38joLDlv/yCksz8vOL/ur6megaGBv91CwA "Perl 5 ‚Äì Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt/), 14 bytes
```
√µ fj w √¶_s√∏666
```
[Test it](https://ethproductions.github.io/japt/?v=1.4.5&code=9SBmaiB3IOZfc/g2NjY=&input=OTY5Njk2)
Seeing as there *was* a 50% time-based bonus: Completes test case `969696` in under half a second.
---
## Explanation
Implicit input of integer `U`.
```
√µ
```
Generate an array of integers from `1` to `U`.
```
fj
```
Filter (`f`) primes.
```
w
```
Reverse.
```
√¶_
```
Return the first element that returns a truthy value (in this case `1`) when passed through a function that checks if ...
```
s√∏666
```
The integer converted to a string (`s`) contains (`√∏`) 666.
---
## Faster Alternative, 15 bytes
Again, seeing as there was originally a time-based bonus, here's an alternative, and much faster, solution which I can't seem to golf any further.
```
U-@j *U¬¥s√∏666}a
```
[Test it](https://ethproductions.github.io/japt/?v=1.4.5&code=VS1AaiAqVbRz+DY2Nn1h&input=OTY5Njk2)
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), 128 bytes
```
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--}
```
[Try it online!](https://tio.run/##HY1RCsIwEESvUmGFhBJEPyJSepilJnYhTWqbohD27HHj55uZx6zp47Z9diHUuuKGi4Ko/RGnTCl2XgHq4tOmgMbbAGhe@aoLeXWS5gykdQGS/DICsQu7E@x7Zm7OfwjRLJin2VprMD4bu7fyndw0OQ7uS5klNVxrldXj/gM "PowerShell ‚Äì Try It Online")
PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on [Prime Factors Buddies](https://codegolf.stackexchange.com/a/94323/42963).
We take input `$n`, then declare a new `function f` that calculates out the factors of input `$a`. If the input `$a` is prime, then this will return just `$a`.
The main part of the program is the infinite `for()` loop. Inside the loop, we check if `$n` `-match`es against `666` and whether `$n` is prime (i.e., `$n` matches all of the factors of `$n`). If it is, we place `$n` on the pipeline and `exit`, with implicit output. Otherwise, we decrement `$n--` and continue the loop.
[Answer]
# [Python 2](https://docs.python.org/2/), 77 76 bytes
**Edit:** -1 byte thanks to [@Mr.Xcoder](https://codegolf.stackexchange.com/users/59487/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!](https://tio.run/##RYzLDsIgEEXX9ismTUxAWViMPJr0S9SkqEVJKC0tC/x6hG68s7mT3HPmb/hMjibd3ZJV4@OlILajisiDnhbwYBwsyr0HFI8NNrpmjNXG9b4/KGuR34dtF/47SjzGOD3VOqzQwTUDlDSnHJKr5ORMBWcXwriQghPJyt2rYilMEW1sW@3mxbiANCp/Vv4A)
## 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!](https://tio.run/##RYzRDoIgGIWv8yn@ubWBcRG0QNx8EnOTSopNUZALe3qCbjrn5uzbzrd@wnuxLOr2Fic1358K9mZWO3IVKjnnpbGDGyo1TcgdA@jFQwBjwSv7GhEjDmOcofvD/UQxjg@1jRu00CUJJfScQtKUglxYLfiVcFHLWhDJc/siS/Ine37frmF9UxxWb2xAGmWWtF8)
# With [SymPy](http://www.sympy.org/en/index.html) 73 bytes
```
lambda x:max(q for q in primerange(0,x+1)if"666"in`q`)
from sympy import*
```
[Try it online!](https://tio.run/##HY1NDsIgFITXcoqXrkBZtDU@2iY9iZoUtSiJ/JR2UU6P4MxmJpnJ5@P2cbZNarylrzSPl4R9MHKnCygXYAFtwQdt5iDte6Y1308N06pCxErbaZkYUcEZWKPxEbTxLmzH9JTrvMII1zxreVNn8Rx7wc9tJ/DCUXR9J3iPxXdSUOVTaP/vQA6ZajeqaOmMpR8)
[Answer]
# [PowerShell](https://github.com/TryItOnline/TioSetup/wiki/Powershell), 71 69 64 bytes
```
param($s)for(;$s-notmatch666-or(2..($s/2)|?{!($s%$_)});$s--){}$s
```
[Try it online!](https://tio.run/##K8gvTy0qzkjNyfn/vyCxKDFXQ6VYMy2/SMNapVg3L78kN7EkOcPMzEwXKGSkpweU1TfSrLGvVgSyVFXiNWs1QQp1NatrVYr///9vaAAEAA "PowerShell ‚Äì 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.
[Answer]
# 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
[Answer]
# Bash + bsd-games package, 33
* 2 bytes saved thanks to @FedericoPoloni.
```
primes 2 $[$1+1]|grep 666|tail -1
```
[Try it online](https://tio.run/##NYyxDsIgFEV3v@IObIakYHxA/JSmA9qnktjS8Bj777QMnrOc6TyjfNs7F1SW@orCSCuIyMIMJz2Dw816R3eQ88E7BOo@MOcLToQrtIb6H9pW0sICCzUqczXT/im89dNeY/pBmzbnldsB).
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 10 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
√º>:√ëb/VP6‚îÄ
```
[Run and debug it](https://staxlang.xyz/#p=813e3aa5622f565036c4&i=6662%0A10000%0A66697%0A328765%0A678987%0A969696&a=1&m=2)
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
```
[Answer]
# [R](https://www.r-project.org/), 57 bytes
```
(a=conf.design::primes(scan():1))[which(grepl(666,a))[1]]
```
-42 bytes from Dominic Van Essen's enormous golf.
uses `grepl` to coerce values to string(since 666 cannot be considered a regex) and check for truthy values.
Runs through the array in reverse to save 2 bytes.
# [R](https://www.r-project.org/) + `conf.design`, ~~81 78~~ 99 bytes
```
library(conf.design);function(n){a=primes(1:n)
a[max(which(grepl("666",as.character(a),fixed=T)))]}
```
[Try it on rdrr.io!](https://rdrr.io/snippets/embed/?code=library(conf.design)%0Ax%3Dfunction(n)%7B%0Aa%3Dprimes(1%3An)%0Aa%5Bmax(which(grepl(%22666%22%2Cas.character(a)%2C%20fixed%3DT)))%5D%7D%0Ax(6666))
My first R solution.
+21 bytes after including library name.
A simple filter. grepl returns true at indices with 666, which returns the truthy indices, and max gets the required index of the prime.
[Answer]
# MATL, 16 bytes
```
ZqP"@V'666'Xf?@.
```
Try it at [MATL Online](https://matl.io/?code=ZqP%22%40V%27666%27Xf%3F%40.&inputs=30000&version=20.4.0)
**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
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~85 83~~ 80 bytes
[Halvard's](https://codegolf.stackexchange.com/a/140505/59487) 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!](https://tio.run/##K6gsycjPM/6fZhvzPycxNyklUSHbKjexQqNCIS2/SKFCITNPoSgxLz1VI1vbUDMzTcnMzEwJKFZcUqRRoamVmJOjUaGaCVabiVBrpFOhqan5v6AoM69EI03D0AAIgHwA "Python 3 ‚Äì Try It Online")
Give it some time, it's extremely slow because of its `O(n^2)` complexity.
[Answer]
# 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](https://codegolf.stackexchange.com/a/91309/69583).
## 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)}`))
```
[Answer]
# 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).
[Answer]
# [PHP](https://php.net/), 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!](https://tio.run/##JcpBCsIwEEDRq0QYaUJd1Ba6ScceJHQRamIC0kwz1Y149hjwb9@nQKVMMwUSQGj6RQOjWbRPWULEQUOcEGx@vM21Wmxb9anm7BokkLAsYFfR1/cMOyJ2ak3bEbeXE70GMgtC1NX5yJS4bpdmHMdGnRC9fbJTwP/n69aQhNvuEljp@VZKGbraDw "PHP ‚Äì Try It Online")
[Answer]
# [Perl 6](http://perl6.org/), 35 bytes
```
my&f={/666/&&.is-prime??$_!!f $_-1}
```
[Try it online!](https://tio.run/##FYtLCoAgFEW3chNx1s/oqfRbijRQCIrERhGt3eyeyeHADS7ulNJxCz89NRHVQlTbVYa4HW5ZuC0KD27L9k0DrvUG4xbTjOevL4M/I8Z8k2ibPGQ1Cp3UinqQ0kYrGPqZh/QB "Perl 6 ‚Äì Try It Online")
Straightforward recursive solution.
[Answer]
# [C# (.NET Core)](https://www.microsoft.com/net/core/platform), 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!](https://tio.run/##NY5BS8QwEEbPza8YikrCbku7YhXS9CJ4Uljcg@eQTXRKTUqSrkjpb6@p6G2@x4N5KhTKeb1OAe07nL5D1J@cqEGGAEcykyxEGVHBxeEZXiRaykiWcHaRHiwIQBvLo/RB00dngxt0@arl@RmtpozxJD5NVrXJ2m9qByZNEKsR3Wycp4kBCsOxqzkWBZs3MIp634sD//rAQdO@RYaG4nW/27U1G0XF0xy76uYqn3HJy/Q4prJA86Zpcsa8jpO3gHz5uyq@rFvKf@Gbx6jpVkLtb@RClvX28HDf3P0A "C# (.NET Core) ‚Äì 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!](https://tio.run/##NY7BSsQwEIbPzVMMRSVht6XdQw@mqQfBk8KiB88hm@qUOC1JuiKlz15TwTkN838z85lQmNHbbQ5IH/D2E6L9ksw4HQKc2cKyEHVEA9cRL/CikbhgWRpnV@2BQAFSLM/aB8sfRwqjs@Wr1ZdnJMuFkAl8msm0iTruaAd92qHZuT1K/YaqW1IAk6qPgzrJ7090lg8tCuw53g6HQ1uLSVXS2zh7gqmr7m7yBde8TA9jMgo8b5omFw943/OiQCHXbb/@7/PuMVrec/rzWdm61VWqXw "C# (.NET Core) ‚Äì 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.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 9 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
√ÖPR.Œî666√•
```
[Try it online.](https://tio.run/##yy9OTMpM/f//cGtAkN65KWZmZoeX/v9vaAAEAA) (No test suite with all test cases, because it's a bit too slow.)
**Explanation:**
```
√ÖP         # Push a list of primes below or equal to the (implicit) input-integer
  R        # Reverse this list
   .Œî      # Find the first value which is truthy for:
     666√•  #  Check whether it contains "666" as substring
           # (after which the found result is output implicitly)
```
The `666` can alternatively be `≈Ω2ƒá` (compressed 666) or `∆µ√©¬∑` (compressed 333 and then doubled).
[Answer]
# Java 8, 77 bytes
```
n->{for(int i=++n;i>1|!(n+"").contains("666");)for(i=--n;n%--i>0;);return n;}
```
[Try it online.](https://tio.run/##PZDBbsIwDIbvPIUXaVKjNhUwLW2J2svO48KRcchCmMKKixqXaWJ99i7tYLZk2b@s77d81BctjvvPwdTae3jVDq8zAIdk24M2FtbjOAlgorEiV0HpZ6F40uQMrAGhHFBU10PTTjuujGNUrlr8PEQYM8ZT0yAFto@YlJJxxafVUghU@CiEq@aKq9ZS1yKg6gc18s/dex34N5tL4/ZwCpBoQ63Dj@0ONP@77u5L1tOL9hZWgPZrPHq7uwbDZbKYh0hCW2TJ0zLP5HMis7zIs6SQY/Z8AgFsvj3ZU9p0lJ6DC9UY3akxW70RizE1/xK/PaMffgE)
**Explanation:**
```
n->{               // Method with integer as both parameter and return-type
  for(int i=++n;   //  Increase the input by 1
                   //  Set `i` to this input+1 (setting `i` to anything above 1 is fine)
      i>1          //  Continue looping as long as `i` is not 0 nor 1
      |!(n+"").contains("666");)
                   //  or if `n` as String does not contain "666" as substring:
    for(i=--n;     //   Decrease `n` by 1 first
                   //   And then set `i` to this new `n`
        n%--i      //   Decrease `i` by 1 before every iteration
             >0;); //   And continue looping as long as `n` does NOT evenly divide `i`
  return n;}       //  After both loops, return the modified `n` as result
```
If `for(i=n;n%--i>0;);` results in \$i<2\$, it means \$n\$ is a prime number (note: [this prime checker](https://codegolf.stackexchange.com/a/100149/52210) only works for \$n\geq2\$, which is fine in this case).
[Answer]
# [Husk](https://github.com/barbuz/Husk), 12 bytes
```
·∏üo`‚Ç¨d666df·πó·π´
```
[Try it online!](https://tio.run/##yygtzv7//@GO@fkJj5rWpJiZmaWkPdw5/eHO1f///zc0AAIA "Husk ‚Äì Try It Online")
]