Skip to main content
Code Golf

Return to Answer

formatting
Source Link
bsoelch
bsoelch
  • 6.1k
  • 1
  • 11
  • 63

floor, 105 bytes

F:x->floor x r:x->1/(x-F x) I:x->1+F(F x-x) p:k->(F k*r k)+1/(r k-1) f:n->(n-1)*I(F p^(n-2)(1+1/(n-1))/n)

returns nonzero for primes and zero for non-primes

Explanation

Ungolfed version:

intPair: x y -> x + 1/y left: x -> floor x right: x -> 1/(x-floor x) is_int: x -> 1+floor(floor x - x) fakt_1: n_k -> intPair ((left n_k)*(right n_k)) (right n_k - 1) f: n -> (n-1)*is_int( (left fakt_1^(n-2) intPair 1 (n-1))/n)

Uses Wilson's theorem to determine if the input is a prime number

fakt_1^(n-2) intPair 1 (n-1) computes (n-1)!+1 (abusing that storing one in the second component of a pair, will increase the first component by 1)

The rest of f checks if (n-1)!+1 is evenly divisible by n and returns 1 if yes and zero otherwise. The multiplication with (n-1) is to ensure that 1 is not falsely detected as prime

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

floor, 116 bytes

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

floor, 116 bytes

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

floor, 105 bytes

F:x->floor x r:x->1/(x-F x) I:x->1+F(F x-x) p:k->(F k*r k)+1/(r k-1) f:n->(n-1)*I(F p^(n-2)(1+1/(n-1))/n)

returns nonzero for primes and zero for non-primes

Explanation

Ungolfed version:

intPair: x y -> x + 1/y left: x -> floor x right: x -> 1/(x-floor x) is_int: x -> 1+floor(floor x - x) fakt_1: n_k -> intPair ((left n_k)*(right n_k)) (right n_k - 1) f: n -> (n-1)*is_int( (left fakt_1^(n-2) intPair 1 (n-1))/n)

Uses Wilson's theorem to determine if the input is a prime number

fakt_1^(n-2) intPair 1 (n-1) computes (n-1)!+1 (abusing that storing one in the second component of a pair, will increase the first component by 1)

The rest of f checks if (n-1)!+1 is evenly divisible by n and returns 1 if yes and zero otherwise. The multiplication with (n-1) is to ensure that 1 is not falsely detected as prime

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>

floor, 116 bytes

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

Source Link
bsoelch
bsoelch
  • 6.1k
  • 1
  • 11
  • 63

floor, 116 bytes

F:x->floor x r:x->1/(x-F x) I:x->-F(F x-x) s:p->I(F p/r p)*F p+1/(1+r p) f:n->-F((1-n)/((1-n)^2+1))*F s^(n-2)(n+1/2)

returns non-zero for primes and zero for composites

Explanation:

Ungolfed version:

lt: x y -> -(floor((x-y)/((x-y)^2+1))) intPair: x y -> x + 1/y left: x -> floor x right: x -> 1/(x-floor x) not_int: x -> -floor(floor x - x) prime_step: n_k -> intPair (not_int(left n_k / right n_k) * left n_k) (1+right n_k) f: n -> (lt 1 n)*(left prime_step^(n-2)(intPair n 2))

prime_step takes a pair of integers (n,k) (encoded as a single rational number) as input an returns (0,k+1) if k is a divisor of n, and (n,k+1) otherwise.

f applies prime_step n-2 times to the pair (n,2) which will return 0 if n is divisible by any integer between 2 and n-1 and n otherwise. The multiplication with lt 1 n is there to ensure that f(1) will return 0

Implementation:

To run the program, execute the Python-script with the arguments

-f <source-file> -- <input-number>