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]

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. — Misha Lavrov, Nov 24 '17 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 '17 at 0:45
@ThePirateBay I don't mean the precise mathematical sense of the word if. I am going to leave it. — Wheat Wizard♦, Nov 25 '17 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. — Wheat Wizard♦, Nov 26 '17 at 19:25

H.PWiz · Accepted Answer · 2017-11-24 21:18:16Z

9

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

edited Nov 24 '17 at 21:18

answered Nov 24 '17 at 20:50

H.PWiz

11.2k2 gold badges16 silver badges55 bronze badges

\$\begingroup\$ Here's a little bit of competition \$\endgroup\$ – Wheat Wizard♦ Nov 26 '17 at 20:23
\$\begingroup\$ @WheatWizard I was hoping someone would post the shorter solution :) \$\endgroup\$ – H.PWiz Nov 26 '17 at 20:24

Add a comment |

ovs · Accepted Answer · 2017-11-25 08:36:43Z

6

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!

edited Nov 25 '17 at 8:36

answered Nov 24 '17 at 22:04

ovs

34.7k2 gold badges20 silver badges97 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

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.

edited Jun 17 '20 at 9:04

Community♦

1

answered Nov 24 '17 at 20:44

Mr. Xcoder

40.9k9 gold badges72 silver badges212 bronze badges

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

Add a comment |

Zgarb · Accepted Answer · 2017-11-25 09:07:32Z

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?

edited Nov 25 '17 at 9:07

answered Nov 25 '17 at 7:31

Zgarb

41.3k4 gold badges72 silver badges249 bronze badges

Add a comment |

Giuseppe · Accepted Answer · 2017-11-28 15:44:16Z

4

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

edited Nov 28 '17 at 15:44

Giuseppe

22.8k3 gold badges26 silver badges91 bronze badges

answered Nov 25 '17 at 22:47

duckmayr

4513 silver badges6 bronze badges

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

Add a comment |

cole · Accepted Answer · 2017-11-24 21:16:54Z

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.

Arnauld · Accepted Answer · 2017-11-24 23:22:33Z

3

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>

edited Nov 24 '17 at 23:22

answered Nov 24 '17 at 22:19

Arnauld

147k14 gold badges150 silver badges535 bronze badges

Add a comment |

Wheat Wizard · Accepted Answer · 2017-12-19 01:47:14Z

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.

DLosc · Accepted Answer · 2017-11-24 21:36:35Z

1

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!

edited Nov 24 '17 at 21:36

answered Nov 24 '17 at 20:52

DLosc

23.2k3 gold badges44 silver badges100 bronze badges

Add a comment |

Steadybox · Accepted Answer · 2017-11-25 02:47:39Z

1

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!

edited Nov 25 '17 at 2:47

answered Nov 25 '17 at 1:03

Steadybox

16k5 gold badges34 silver badges83 bronze badges

Add a comment |

R. Kap · Accepted Answer · 2017-11-25 10:14:39Z

1

dc, ₄₀ ₃₄ 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!

edited Nov 25 '17 at 10:14

answered Nov 25 '17 at 9:46

R. Kap

4,8182 gold badges11 silver badges35 bronze badges

Add a comment |

Uriel · Accepted Answer · 2017-11-25 23:29:29Z

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?

caird coinheringaahing · Accepted Answer · 2021-04-01 20:00:54Z

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

ovs · Accepted Answer · 2017-11-25 22:12:06Z

0

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)

answered Nov 25 '17 at 22:12

ovs

34.7k2 gold badges20 silver badges97 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2017-11-30 01:41:29Z

0

JavaScript ES5, 34 Bytes

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

answered Nov 30 '17 at 1:41

l4m2

7,8931 gold badge12 silver badges43 bronze badges

Add a comment |

caird coinheringaahing · Accepted Answer · 2017-12-03 19:57:03Z

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]

Makonede · Accepted Answer · 2021-04-01 20:52:00Z

0

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

answered Apr 1 at 20:52

Makonede

3,4626 silver badges32 bronze badges

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

Add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Different ways of defining primes

Task

Tests

17 Answers 17

Haskell, 45 bytes

Python 2, 39 37 bytes

Python 3, 45 bytes

How it works

Husk, 6 5 bytes

Explanation

R, 44 37 bytes

J, 30 bytes

Explanation

Notes

JavaScript (ES6), 33 32 30 bytes

Demo

Haskell, 30 bytes

Explanation

Pip, 23 19 14 bytes

C, 55 bytes

dc, ₄₀ ₃₄ 37 bytes

APL (Dyalog), 24 bytes

Jelly, 8 5 bytes

How they work

JavaScript (Node.js), 27 bytes

JavaScript ES5, 34 Bytes

Add++, 20 bytes

05AB1E, 4 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math decision-problem primes or ask your own question.

Linked

Hot Network Questions

Different ways of defining primes

Task

Tests

17 Answers 17

Haskell, 45 bytes

Python 2, 39 37 bytes

Python 3, 45 bytes

How it works

Husk, 6 5 bytes

Explanation

R, 44 37 bytes

J, 30 bytes

Explanation

Notes

JavaScript (ES6), 33 32 30 bytes

Demo

Haskell, 30 bytes

Explanation

Pip, 23 19 14 bytes

C, 55 bytes

dc, 40 34 37 bytes

APL (Dyalog), 24 bytes

Jelly, 8 5 bytes

How they work

JavaScript (Node.js), 27 bytes

JavaScript ES5, 34 Bytes

Add++, 20 bytes

05AB1E, 4 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math decision-problem primes or ask your own question.

Linked

Related

Hot Network Questions

dc, ₄₀ ₃₄ 37 bytes