32
\$\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\$
  • 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\$ – Sriotchilism O'Zaic Nov 25 '17 at 1:29
  • 1
    \$\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\$ – Sriotchilism O'Zaic Nov 26 '17 at 19:25

16 Answers 16

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\$
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\$
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\$
  • \$\begingroup\$ Can't you use & instead of and and >=i instead of >i-1? \$\endgroup\$ – Sriotchilism O'Zaic 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\$ – Sriotchilism O'Zaic 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\$
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\$
  • \$\begingroup\$ Welcome to PPCG! Great first answer! \$\endgroup\$ – FantaC 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\$
1
\$\begingroup\$

Jelly, 8 bytes

rṖ⁴%$Ạ×<

Try it online!

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

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.