Different ways of defining primes

Question

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]

Answer 1

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

Answer 2

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!

Answer 3

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.

Answer 4

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?

Answer 5

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

Answer 6

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.

Answer 7

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>

Answer 8

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.

Answer 9

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!

Answer 10

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!

Answer 11

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!

Answer 12

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?

Answer 13

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

Answer 14

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)

Answer 15

JavaScript ES5, 34 Bytes

for(a=i=(p=prompt)();a%--i;);i<p()

Answer 16

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]

Answer 17

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