18
\$\begingroup\$

The Task

Write a program or function that, when passed a numerical input x, prints or returns the primes beneath the square root of x1 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.

1 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.

\$\endgroup\$
  • 3
    \$\begingroup\$ "Only primes below the square root can actually be involved within the factors of x" isn't true: a number can have one prime factor that's larger than its square root. Indeed, your first two examples (5 and 20) have this property, as do all primes, twice all odd primes, .... \$\endgroup\$ – Greg Martin Dec 9 '16 at 0:34
  • 1
    \$\begingroup\$ @GregMartin Yes, they can - but they cannot be found within the first half of the factors. It makes sense not to include 7 in the missing primes of 48 as 7^2 is greater than 48. (my reasoning lies there) \$\endgroup\$ – Addison Crump Dec 9 '16 at 1:47

19 Answers 19

8
\$\begingroup\$

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}
\$\endgroup\$
  • 5
    \$\begingroup\$ Jelly answers often just literally describe the challenge :P \$\endgroup\$ – ETHproductions Dec 9 '16 at 2:48
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I never tried MATLAB, but according to what I read about it, sqrt(p) can be written as p^0.5 or maybe p^.5 although I am not sure about the second suggestion \$\endgroup\$ – t-clausen.dk Dec 9 '16 at 12:40
  • \$\begingroup\$ Nice! :) I posted an Octave submission using the same approach. \$\endgroup\$ – Stewie Griffin Dec 10 '16 at 0:06
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 8 bytes

tLDpϹfK

Try it online!

Explanation

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

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.

\$\endgroup\$
2
\$\begingroup\$

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].

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Very nice, will have to look into Octave. Those features would be helpful for golf! \$\endgroup\$ – MattWH Dec 10 '16 at 0:21
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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] ]
\$\endgroup\$
  • \$\begingroup\$ Save a byte with gcd(z*x)y>1. \$\endgroup\$ – Zgarb Dec 15 '16 at 18:31
  • \$\begingroup\$ I've also put the y*y<x check first to make it a bit faster. \$\endgroup\$ – James Hollis Dec 16 '16 at 23:28
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.