# Different ways of defining primes

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.

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]
• n=6, a=15 is the first interesting test case.
– Neil
Nov 24, 2017 at 20:47
• 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. Nov 24, 2017 at 21:36
• "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?
– user72349
Nov 25, 2017 at 0:45
• @ThePirateBay I don't mean the precise mathematical sense of the word if. I am going to leave it. Nov 25, 2017 at 1:29
• @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. Nov 26, 2017 at 19:25

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 • Here's a little bit of competition Nov 26, 2017 at 20:23 • @WheatWizard I was hoping someone would post the shorter solution :) Nov 26, 2017 at 20:24 # 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! # 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. • Can't you use & instead of and and >=i instead of >i-1? Nov 24, 2017 at 20:47 • @WheatWizard >=i is still 4 bytes (because of the space). – Neil Nov 24, 2017 at 20:49 • @Neil If you change to & you don't need the space. Nov 24, 2017 at 20:49 # Husk, 6 5 bytes εf≥⁰Ḋ 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? # 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 • Welcome to PPCG! Great first answer! – qqq Nov 25, 2017 at 23:09 # 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. # JavaScript (ES6), 3332 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> # 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.

# Pip, 2319 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!

# 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!

# dc, 4034 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!

# 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?

# 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

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

# JavaScript ES5, 34 Bytes

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

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]