33
\$\begingroup\$

One of my favorite definitions of the prime numbers goes as follows:

  • 2 is the smallest prime.

  • Numbers larger than 2 are prime if they are not divisible by a smaller prime.

However this definition seems arbitrary, why 2? Why not some other number? Well lets try some other numbers will define n-prime such that

  • n is the smallest n-prime.

  • Numbers larger than n are n-prime if they are not divisible by a smaller n-prime.

Task

The task here is to write a program that takes two inputs, a positive integer n and a positive integer a. It will then decide if a is n-prime. Your program should output two distinct values one for "yes, it is n-prime" and one for "no, it is not n-prime".

This is a code-golf question so answers will be scored in bytes with less bytes being better.

Tests

Here are lists of the first 31 primes for n=2 to n=12 (1 is the only 1-prime number)

n=2: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=3: [3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=4: [4,5,6,7,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=5: [5,6,7,8,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=6: [6,7,8,9,10,11,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=7: [7,8,9,10,11,12,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=8: [8,9,10,11,12,13,14,15,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=9: [9,10,11,12,13,14,15,16,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=10: [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=11: [11,12,13,14,15,16,17,18,19,20,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=12: [12,13,14,15,16,17,18,19,20,21,22,23,25,27,29,31,33,35,37,41,43,47,49,53,55,59,61,67,71,73,77]
\$\endgroup\$
9
  • 4
    \$\begingroup\$ n=6, a=15 is the first interesting test case. \$\endgroup\$ – Neil Nov 24 '17 at 20:47
  • 6
    \$\begingroup\$ It's the first place where the non-pattern "a is n-prime iff n≤a<2n or (a≥2n and a is prime)" breaks down. \$\endgroup\$ – Misha Lavrov Nov 24 '17 at 21:36
  • 2
    \$\begingroup\$ "Numbers larger than 2 are prime if they are not divisible by a smaller prime." - This definition allows any number to be prime. Maybe you want to say iff instead of if? \$\endgroup\$ – user72349 Nov 25 '17 at 0:45
  • 5
    \$\begingroup\$ @ThePirateBay I don't mean the precise mathematical sense of the word if. I am going to leave it. \$\endgroup\$ – Wheat Wizard Nov 25 '17 at 1:29
  • 2
    \$\begingroup\$ @JeppeStigNielsen It's not very hard to prove this. All composite numbers that are n-prime must have only prime factors that are smaller than n. We also know that no subset of their factors can have a product larger than n because our number would be divisible by that. Thus every n-prime is either 2-prime or the product of 2 numbers less than n. There are only a finite number of pairings of numbers less than n, thus there are only a finite number of composite n-prime numbers. Hopefully that makes sense, I had to abbreviate to fit it in a comment. \$\endgroup\$ – Wheat Wizard Nov 26 '17 at 19:25

17 Answers 17

9
\$\begingroup\$

Haskell, 45 bytes

n!a=not$any(n!)[x|x<-[n..a-1],mod a x<1]||n>a

Try it online!

I define a nice recursive function (!):

n!a checks if any factor of a, in the range [n,a-1], is an n-prime. Then it negates the result. It also makes sure that n>a

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

Python 2, 39 37 bytes

Thanks to Halvard Hummel for -2 bytes.

f=lambda n,i:n==i or i>i%n>0<f(n+1,i)

Try it online!

\$\endgroup\$
0
4
\$\begingroup\$

Python 3, 45 bytes

lambda i,k:(i>k)<all(k%r for r in range(i,k))

Try it online!

How it works

This takes two integers as input, i and k. First checks if k ≥ i. Then generates the range [i, k) and for each integer N in this range, checks if N is coprime to k. If both conditions are fulfilled, then k is an i-prime.

\$\endgroup\$
3
  • \$\begingroup\$ Can't you use & instead of and and >=i instead of >i-1? \$\endgroup\$ – Wheat Wizard Nov 24 '17 at 20:47
  • \$\begingroup\$ @WheatWizard >=i is still 4 bytes (because of the space). \$\endgroup\$ – Neil Nov 24 '17 at 20:49
  • \$\begingroup\$ @Neil If you change to & you don't need the space. \$\endgroup\$ – Wheat Wizard Nov 24 '17 at 20:49
4
\$\begingroup\$

Husk, 6 5 bytes

εf≥⁰Ḋ

Try it online! or see results up to 80.

Thanks to Leo for -1 byte.

Explanation

εf≥⁰Ḋ  Inputs are n and k.
    Ḋ  Divisors of k.
 f     Keep those that are
  ≥⁰   at least n.
ε      Is the result a one-element list?
\$\endgroup\$
0
4
\$\begingroup\$

R, 44 37 bytes

function(a,n)a==n|a>n&all(a%%n:(a-1))

Try it online!

-7 bytes thanks to Giuseppe

Returns TRUE if

  • a is equal to n or (a==n|)
  • a is greater than n and (a>n&) for every number k from n to a-1, a is not evenly divisible by k (all(a%%n:(a-1)))

Returns FALSE otherwise

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG! Great first answer! \$\endgroup\$ – RaviRavioli Nov 25 '17 at 23:09
3
\$\begingroup\$

J, 30 bytes

>:*(-{1=[:+/0=[:|/~]+i.@[)^:>:

Try it online!

Takes starting value as the right argument and the value to check at the left argument.

I messed up originally and didn't account for left arguments less than the starting prime. I'm somewhat unhappy with the length of my solution now.

Explanation

Let x be the left argument (the value to check) and y be the right argument (the starting prime).

>:*(-{1=[:+/0=[:|/~]+i.@[)^:>:
                          ^:>:  Execute left argument if x >= y
                     i.@[         Create range [0..x]
                   ]+             Add y to it (range now: [y..x+y])
                |/~               Form table of residues
            0=                    Equate each element to 0
          +/                      Sum columns
      1=                          Equate to 1
    -{                            Take the element at position x-y
>:*                             Multiply by result of x >= y

Notes

The element at position x-y is the result of primality testing for x (since we added y to the original range).

Multiplying by x >: y ensures that we get a falsey value (0) for x less than y.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 33 32 30 bytes

Takes input in currying syntax (n)(a). Returns a boolean.

n=>p=(a,k=a)=>k%--a?p(a,k):a<n

Demo

let f =

n=>p=(a,k=a)=>k%--a?p(a,k):a<n

for(n = 2; n <= 12; n++) {
  for(a = n, P = []; P.length < 31; a++) {
    f(n)(a) && P.push(a);
  }
  O.innerText += 'n=' + n + ': ' + P.join(',') + '\n';
}
<pre id=O></pre>

\$\endgroup\$
3
\$\begingroup\$

Haskell, 30 bytes

2 bytes saved thanks to H.PWiz's idea which was borrowed from flawr's answer

n!a=[1]==[1|0<-mod a<$>[n..a]]

Try it online!

Ok since its been a while, and the only Haskell answer so far is 45 btyes, I decided to post my own answer.

Explanation

This function checks that the only number between n and a that a is divisible by is a itself.

Now the definition only mentions n-primes smaller than a, so why are we checking all these extra numbers? Won't we have problems when a is divisible by some n-composite larger than n?

We won't because if there is an n-composite larger than n it must be divisible by a smaller n-prime by definition. Thus if it divides a so must the smaller n-prime.

If a is smaller than n [n..a] will be [] thus cannot equal [1] causing the check to fail.

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

Pip, 23 19 14 bytes

b>=a&$&b%(a,b)

Shortest method is a port of Mr. Xcoder's Python answer. Takes the smallest prime and the number to test as command-line arguments. Try it online!

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

C, 55 bytes

f(n,a,i){for(i=a;i-->n;)a%i||f(n,i)&&(i=0);return-1<i;}

Try it online!

53 bytes if multiple truthy return values are allowed:

f(n,a,i){for(i=a;i-->n;)a%i||f(n,i)&&(i=0);return~i;}

Try it online!

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

dc, 40 34 37 bytes

[0p3Q]sf?se[dler%0=f1+dle>u]sudle>u1p

I would have included a TIO link, but TIO seems to be carrying a faulty distribution of dc seeing as how this works as intended on my system but the Q command functions erroneously on TIO. Instead, here is a link to a bash testing ground with a correctly functioning version of dc:

Demo It!

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

APL (Dyalog), 24 bytes

{⍵∊o/⍨1=+/¨0=o|⍨⊂o←⍺↓⍳⍵}

Try it online!

How?

⍳⍵ - 1 to a

o←⍺↓ - n to a, save to o

o|⍨⊂o - modulo every item in o with every item in o

0= - check where it equals 0 (divides)

+/¨ - sum the number of divisions

1= - if we have only one then the number is only divided by itself

o/⍨ - so we keep these occurences

⍵∊ - is a in that residual array?

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

Jelly, 8 5 bytes

rḍṛċ<

Try it online!

This outputs 0 or 1 for "yes" and a positive integer greater than 1 for "no". This really stretches the "output two distinct values", so I've included a more reasonable 6 byte version:

rḍṛṖi<

Try it online!

Outputs 0 for "yes, it is \$n\$-prime" and a positive integer for "no it is not \$n\$-prime". +1 byte to use just 0 and 1.

How they work

rḍṛċ< - Main link. Takes n on the left and a on the right
r     - Range from n to a inclusive
  ṛ   - Right; Yield a
 ḍ    - For each element in the range, is it divisible by a?
    < - Is n < a?
   ċ  - Count the occurrences of (n < a) in the divisibility range

This works because in the range \$[n, a]\$, only one integer can be divisible by \$a\$ if \$a\$ is \$n\$-prime: \$a\$. Therefore, the range, after divisibility, would look like [0, 0, 0, ..., 1]. However, this doesn't check the condition that \$n\$ is the smallest \$n\$-prime, as r will generate a descending range if \$n < a\$. Therefore, we check that \$n < a\$ and count the occurrences of that (1 or 0) in the divisibility range. If \$n > a\$, there will be more than one 0 in the range, and if \$a\$ is not \$n\$-prime, but \$n < a\$, there will be more than 1 in the range.

If \$n = a\$, then r will yield an empty list and ċ will return 0, no matter what the result of < is.

rḍṛṖi< - Main link. Takes n on the left and a on the right
r      - Range from n to a inclusive
  ṛ    - Right; Yield a
 ḍ     - For each element in the range, is it divisible by a?
   Ṗ   - Remove the final element, 1
     < - Is n < a?
    i  - Index of (n < a) or 0 if not found
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 27 bytes

i=>f=n=>i==n||i>i%n&&f(n+1)

Try it online!

Port of my Python answer, takes input in currying syntax: m(number)(first prime)

\$\endgroup\$
0
\$\begingroup\$

JavaScript ES5, 34 Bytes

for(a=i=(p=prompt)();a%--i;);i<p()
\$\endgroup\$
0
\$\begingroup\$

Add++, 20 bytes

L,2Dx@rBcB%B]b*!!A>*

Try it online!

L,   - Create a lambda function
     - Example arguments:  [5 9]
  2D - Copy below; STACK = [5 9 5]
  x  - Repeat;     STACK = [5 9 [9 9 9 9 9]]
  @  - Reverse;    STACK = [[9 9 9 9 9] 5 19] 
  r  - Range;      STACK = [[9 9 9 9 9] [5 6 7 8 9]]
  Bc - Zip;        STACK = [[9 5] [9 6] [9 7] [9 8] [9 9]]
  B% - Modulo;     STACK = [4 3 2 1]
  B] - Wrap;       STACK = [[4 3 2 1]]
  b* - Product;    STACK = [24]
  !! - Boolean;    STACK = [1]
  A  - Arguments;  STACK = [1 5 9]
  >  - Greater;    STACK = [1 1]
  *  - Product;    STACK = [1]
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 4 bytes

ћ_O

Try it online! Beats all other answers.

ћ_O  # full program
   O  # sum of...
 ›    # is...
      # implicit input...
  _   # not...
 ›    # greater than...
      # (implicit) each element of...
Ñ     # divisors of...
      # implicit input
      # implicit output
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Fails for n = 8, a = 16 \$\endgroup\$ – caird coinheringaahing Apr 1 at 20:55
  • \$\begingroup\$ @ChartZBelatedly No, it doesn't. \$1\$ is the only truthy value in 05AB1E, which is what allows me to shorten my code using O. \$\endgroup\$ – Makonede Apr 1 at 20:57
  • \$\begingroup\$ I'm not sure I understand how this answer is supposed to work; the explanation is not really meaningful to me; but 15 6 gives 1, 16 6 gives 2, and 18 6 gives 3 so there is obviously some sort of failure going on. \$\endgroup\$ – Wheat Wizard Apr 1 at 21:38
  • \$\begingroup\$ @WheatWizard As I just said, there is no failure. \$1\$ is the only truthy value in 05AB1E, and so only the inputs returning 1 are giving a truthy output. \$\endgroup\$ – Makonede Apr 1 at 22:15
  • \$\begingroup\$ The program outputs 3 different things. It doesn't matter what they are, you can only output two values, and this outputs 3. I don't have to know anything about the language or how this answer works to know that this can't be correct. \$\endgroup\$ – Wheat Wizard Apr 1 at 23:37

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.