Print the missing primes

Question

The Task

Write a program or function that, when passed a numerical input x, prints or returns the primes beneath the square root of x¹ that are not factors of x.

Examples

Let f(x) be the function called:

>>> f(4)
[]

>>> f(5)
[2]

>>> f(20)
[3]

>>> f(60)
[7]

>>> f(100)
[3, 7]

>>> f(10000)
[3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Bonus Rules

• You may use any builtins that your language provides.
• Your program must support an x input as high as the upper bound defined by your language.

---

¹ Using the square root as only primes below the square root can actually be involved within the factors of x. Without making this restriction, larger numbers would have a lot of excess printed numbers.

Answer 1

Jelly, 6 bytes in Jelly's codepage

½ÆRḟÆf

Try it online!

Explanation:

½ÆRḟÆf
 ÆR    All primes less than or equal to
½      the square root of the input
   ḟ   but with the following removed:
    Æf All prime factors of {the input, by default}

Answer 2

MATL, 10 9 bytes

X^ZqGYfX-

Try it online!

Explanation

X^    % Implicit input. Square root
Zq    % Array if primes up to that
G     % Push input again
Yf    % Array of prime factors
X-    % Set difference. Implicit display

Answer 3

Python 3, 67 62 bytes

f=lambda n,k=1,m=1:k*k<n and(m%k*n%k>0)*[k]+f(n,k+1,m*k*k)or[]

Try it online!

Answer 4

MATLAB, 57 54 bytes

function h(p);a=primes(p^.5);a(~ismember(a,factor(p)))

Pretty straightforward, gets an array of primes up to sqrt(p) then removes any that are also factors of p. Prints the output of the last line by default because the semicolon is left off.

Answer 5

Pyth, 10 bytes

fP_T-S@Q2P

A program that takes input of a number and prints a list.

Test suite

How it works

fP_T-S@Q2P   Program. Input: Q
fP_T-S@Q2PQ  Implicit input fill
f            Filter
     S@Q2    the 1-indexed range up to floor(sqrt(Q))
    -    PQ  with the prime factors of Q removed
 P_T         by primality
             Implicitly print

Answer 6

05AB1E, 8 bytes

tLDpϹfK

Try it online!

Explanation

tL        # range [1 ... sqrt(input)]
  DpÏ     # keep only primes
     ¹fK  # remove factors of input

Answer 7

PHP, 76 bytes

for($n=1;++$n*$n<$x=$argv[1];){for($i=$n;$n%--$i;);if($i<2&&$x%$n)echo$n,_;}

uses my is_prime solution golfed for $n>1

takes input from command line argument. Run with -r.

Answer 8

JavaScript (ES6), 79 76 bytes

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]

Based on my recursive primality test function. I feel like there should be a few ways to simplify this, but I can't figure out how...

Test snippet

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]

<input type="number" step=1 min=4 value=4 oninput="O.innerHTML='['+f(this.value)+']'"><br>
<pre id=O>[]</pre>

Answer 9

Mathematica, 46 bytes

Select[Prime@Range@PrimePi@Sqrt[a=#],!#∣a&]&

Anonymous function. Takes a number as input and returns a list of numbers as output. The Unicode character is U+2223 DIVIDES for \[Divides].

Answer 10

Ruby, 55 bytes

require'prime'
->x{Prime.to_a(x**0.5).select{|n|x%n>0}}

A rather lazy answer using the builtin prime enumerator.

Answer 11

Wonder, 14 bytes

@(_> > ^#0.5)P

Usage:

(@(_> > ^#0.5)P)10

Takes items from an infinite list of primes while the item is less than the square root of the argument.

Answer 12

Pyke, 10 bytes

,BS#_P)QP-

Try it here!

,B         -    int(sqrt(input))
  S        -   range(1, ^+1)
   #_P)    -  filter(^, is_prime)
         - - ^.remove(V)
       QP  -  factors(input)

Answer 13

PowerShell v2+, 71 bytes

param($n)1..[math]::Sqrt($n)|?{$n%$_-and'1'*$_-match'^(?!(..+)\1+$)..'}

Iterative solution. Takes input $n and creates a range from 1 to the Sqrt($n) (note that the range operator will implicitly cast the upper end to an [int] which will do Banker's Rounding by default). Then uses |?{...} (the Where-Object operator, which acts like a filter) to pull out those numbers where $n%$_ is non-zero (i.e., any remainder to the modulo means it's not a factor, and any non-zero is truthy) -and the usual regex prime test is $true. Those are left on the pipeline, and output is implicit.

Examples

(with some extra formatting to pretty up the output)

PS C:\Tools\Scripts\golfing> 5,20,60,100,10000|%{"f($_)";(.\print-the-missing-primes.ps1 $_)-join', ';""}
f(5)
2

f(20)
3

f(60)
7

f(100)
3, 7

f(10000)
3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

---

NB - This will fail on earlier versions if the input is bigger than around 2500000000, because the .. range operator can only support up to 50,000 items. But, since that is bigger than the default [int] datatype's max value, 2147483647, I'm presuming that to be OK. On my machine, PSv4 Win8.1, however, I can go higher, but I'm not able to find documentation explaining the difference.

Answer 14

Octave, 44 bytes

This answer is inspired by MattWH's MATLAB answer, but I've golfed it using some Octave-specific features.

@(x)(y=primes(x^.5))(~ismember(y,factor(x)))

This is an anonymous function that takes the input x. Octave has inline variable assignment and indexing allowing y to first be created in the function (not possible in MATLAB), then used as part of the logical mask created by ismember (again, not possible to do it this way in MATLAB).

Answer 15

Perl 6, 37 bytes

{grep {$^a.is-prime&$_%$a},2.. .sqrt}

Expanded:

{   # bare block lambda with implicit parameter ｢$_｣

  grep
  {
    $^a.is-prime  # check if it is prime
    &             # and junction
    $_ % $a       # check if the input is not evenly divisible by it
  },
  2.. .sqrt          # Range of values up-to and including squareroot
}

Answer 16

TSQL, 130 bytes

DECLARE @v int=10000

,@ INT=2SELECT 2p INTO #
g:INSERT # SELECT @ FROM # HAVING isnull(min(@%p),1)>0SET @+=1IF @*@<@v GOTO g
SELECT*FROM # WHERE @v%p>0

This will only execute once, then you need to drop the temp table to execute again in the same editor

DROP TABLE #

I made a version to test it, it is a bit longer because the online permissions for creating tables is unavailable. For the same reason it doesn't need the drop table though.

Try it online

Answer 17

R, 58 63 bytes

for(i in 2:sqrt(x<-scan()))if(x%%i&numbers::isPrime(i))print(i)

Loops over all values from 2 to sqrt(x) and checks if they are prime with the numbers package. x%%i calculates x mod i which is 0 -> False if i is a divisor of x and >0 -> True if i is not.

+5 bytes because the numbers::Primes(n) function doesn't allow decimals, while 2:sqrt(x) does work, added prime check to if statement.

Answer 18

Haskell, 55 54 bytes

f x=[y|y<-[2..x],y*y<x,[z|z<-[1..y],gcd(z*x)y>1]==[y]]

Mostly straightforward nested list comprehensions. GCD performs two roles, testing whether the numbers below y are factors of y and also testing whether y is a factor of x.

Spaced out a little:

f x = [ y|y<-[2..x],     y*y<x,     [z|z<-[1..y], gcd (z*x) y > 1] == [y] ]

Answer 19

Retina, 69 66 bytes

.+
$*
(11\1|^1)+
$#1$*1:$&
M!&`(?!(11+)\1+:)(1+):(?!\2+$)
M%`1
^0

Prints the primes on separate lines, from largest to smallest.

Try it online! (Takes about 10 seconds due to the last two test cases. The header and footer enable a linefeed-separate test suite, and convert the output to comma-separation for readability.)

Explanation

.+
$*

Convert the input to unary.

(11\1|^1)+
$#1$*1:$&

This prepends the square root of the input, separated by :. The square root is computed based on the fact that the square of n is also the sum of the first n odd integers. We can match consecutive odd integers with the forward reference (11\1|^1). In the process the group will be used exactly n times, where n is the largest number whose square fits into the input.

We insert a unary representation of this number with $#1$*1, followed by a colon and the match itself.

M!&`(?!(11+)\1+:)(1+):(?!\2+$)

This matches all the missing primes that fit into the square root. The prime detection is based on the standard prime checking regex, and then we simply make sure that the prime we've just captured does not divide the input with the second lookahead. By using the & option, we get overlapping matches to ensure that we get all primes.

M%`1

This converts each line (i.e. each missing prime) back to decimal by matching the number of 1s. The only issue is that this inserts a zero if no missing primes were found at all.

^0

So this stage removes that zero if it was added.