Prime or highest factor

Question

Challenge:

Given an array of non-negative whole numbers numbers in the range of 0 to Infinity, Check whether all of them are primes or not. (You can take input as a string too if you want)

Input:

Input: An array of numbers

Output: The array with every element replaced by one of these:

-1                 -----> If 0, 1
1                  -----> If it is a prime number greater than 1
the highest factor -----> If that number is not prime

Return either -1 (0, 1), 1 (for primes >= 2) or the highest factor of given number (for non-primes)

Examples:

[1, 2, 3, 4, 10, 11, 13]                        ---> [-1, 1, 1, 2, 5, 1, 1]
[100, 200, 231321, 12312, 0, 111381209, 123123] ---> [50, 100, 77107, 6156, -1, 1, 41041]

Note:

Input will always be valid, i.e it will consist only of numbers and decimals are not tested for. The array can be empty, if so, return the empty array.

Restriction:

This is code-golf so shortest code in bytes for each language wins.

LeaderBoard :

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=163882,OVERRIDE_USER=8478;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Jelly,  7 6 bytes

ÆḌṪ€o-

A monadic link accepting a list of non-negative integers and returing a list of integers greater than or equal to -1.

Try it online!

How?

Note that:

• All primes have a single proper divisor (one)
• All composites have multiple proper divisors (one plus the others)
• No number has itself as a proper divisor
• Jelly's get-proper-divisors atom, ÆḌ, yields a list of proper divisors in ascending order
• Zero and one have no proper divisors (they are neither prime, nor composite)
• Applying Jelly's tail atom, Ṫ, to an empty list yields zero
• No number has a proper divisor of zero (let alone being the maximal one)
• All non-zero numbers are truthy in Jelly, while zero is falsey

ÆḌṪ€o- | Link: list of integers   e.g. [ 0, 1,  2,  5,     10,    5183]
ÆḌ     | proper divisors (vectorises)  [[],[],[1],[1],[1,2,5],[1,71,73]]
  Ṫ€   | tail €ach                     [ 0, 0,  1,  1,      5,      73]
     - | literal minus one
    o  | logical OR (vectorises)       [-1,-1,  1,  1,      5,      73]

Answer 2

Jelly, 9 8 bytes

Saved 1 byte thanks to @Dennis

:ÆfṂ€$~~

Try it online! or run all test cases

Commented

We take advantage of the fact that both nan and inf become 0 in Jelly when a bitwise NOT is applied to them.

:ÆfṂ€$~~ - main link, taking the input list
 ÆfṂ€$   - treat these two links as a monad:
 Æf      -   get the lists of prime factors (0 --> 0; 1 --> empty list; prime --> itself)
    €    -   for each list,
   Ṃ     -   isolate the minimum prime factor (turns empty lists into 0)
:        - divide each entry by its minimum prime factor (0/0 --> nan; 1/0 --> inf)
      ~~ - bitwise NOT x2 (nan or inf --> 0 --> -1; other entries are unchanged)

Answer 3

R, 68 62 bytes

Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())

A solution using only base R, no libraries! Thanks to Giuseppe for golfing away 6 bytes.

Uses scan to read in a space separated list of numbers, %% to identify which are factors. v then contains a vector of all factors in ascending order (including 1 and n). This has the nice property that when we reverse v, the number we want will be in the second place, avoiding an expensive call to length or tail(if n was prime, v contains n 1, else it contains n (factors in descending order) 1).

Example output (TIO link here):

> Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())
1: 0 1 2 3 4 5 6 7 8 9
11: 
Read 10 items
[[1]]
[1] -1

[[2]]
[1] -1

[[3]]
[1] 1

[[4]]
[1] 1

[[5]]
[1] 2

[[6]]
[1] 1

[[7]]
[1] 3

[[8]]
[1] 1

[[9]]
[1] 4

[[10]]
[1] 3

If you think a list is not an acceptable return type, then swap out Map for sapply and add 3 bytes.

Answer 4

05AB1E, 11 9 8 bytes

Ñε¨àDd<+

-3 bytes thanks to @Emigna, changing ©d1-®+ to Dd<+ and ۬ۈ to ε¨à.

Only my second 05AB1E answer, so can definitely be golfed.

Try it online.

Explanation:

Ñ           # Divisors of each item in the input-list (including itself)
            #  [1,2,10,3] → [[1],[1,2],[1,2,5,10],[1,2,3]]
 ε          # For each:
  ¨         #  Remove last item (so it's now excluding itself)
            #   [[1],[1,2],[1,2,5,10],[1,2,3]] → [[],[1],[1,2,5],[1,2]]
   à        #  And get the max
            #   [[],[1],[1,2,5],[1,2]] → ['',1,5,2]
    D       # Duplicate the list
     d      # Is it a number (1 if it's a number, 0 otherwise)
            #  ['',1,5,2] → [0,1,1,1]
      <     # Subtract 1
            #  [0,1,1,1] → [-1,0,0,0]
       +    # Add both lists together
            #  ['',1,5,2] and [-1,0,0,0] → ['-1',1,5,2]

Answer 5

J, 21 bytes

_1:`(%{.@q:)@.(>&1)"0

Try it online!

Explanation:

(>&1)"0 is each number greater than 1?

@. if not, return _1:

(%{.@q:) if its 2 or greater, divide % the number by the first {.of the prime factors q:

Answer 6

Japt, 6 bytes

After golfing, ended up being almost identical to, and just as short as, Jonathan's solution.

®â¬ÌªJ

Try it

---

Explanation

®          :Map
 ⬠       :  Proper divisors
   Ì       :  Get last element (returns null if the array is empty)
    ª      :  Logical OR
     J     :  -1

Answer 7

Python 3, 62 bytes

lambda l:[max([k for k in range(1,n)if n%k<1]+[-1])for n in l]

Try it online!

For 0 and 1 range(1,n) is empty, therefore the code evaluates to max([]+[-1]) = -1. For prime numbers, the only divisor in the [1, n) is 1, which is the desired output.

---

Coconut, 50 bytes

map$(n->max([k for k in range(1,n)if n%k<1]+[-1]))

Try it online!

Answer 8

Java 8, 105 103 87 bytes

a->{for(int i=a.length,n,x;i-->0;a[i]=n<2?-1:n/x)for(n=a[i],x=1;++x<n;)if(n%x<1)break;}

Modifies the input-array instead of returning a new one to save bytes.

Try it online.

Explanation:

a->{                  // Method with integer-array parameter and no return-type
  for(int i=a.length,n,x;i-->0;
                      //  Loop backward over the array
      a[i]=           //    After every iteration: change the current item to:
           n<2?       //     If the current item is 0 or 1:
            -1        //      Change it to -1
           :          //     Else:
            n/x)      //      Change it to `n` divided by `x`
     for(n=a[i],      //   Set `n` to the current item
         x=1;++x<n;)  //   Inner loop `x` in range [2,`n`)
       if(n%x<1)      //    If `n` is divisible by `x`:
         break;}      //     Stop the inner loop (`x` is now the smallest prime-factor)
                      //   (if the loop finishes without hitting the `break`,
                      //    it means `n` is a prime, and `x` and `n` will be the same)

Answer 9

Haskell, 52 49 bytes

map(\x->last$[d|d<-[1..x-1],mod x d<1]++[-1|x<2])

Try it online!

map                     -- for each element in the input array
  \x->                  -- apply the lambda function
    last                -- pick the last element of the following list
     [d|d<-[1..x-1]     --  all d from 1 to x-1 
           ,mod x d<1]  --    where d divides x 
     ++[-1|x<2]         --  followed by -1 if x<2

Answer 10

Husk, 8 bytes

m(|_1→hḊ

Try it online!

Explanation

m(|_1→hḊ  Implicit Input         [1,2,3,4,10]
m(        Map each element
       Ḋ    List of divisors     [[1],[1,2],[1,3],[1,2,4],[1,2,5,10]]
     →h     Penultimate element  [0,1,1,2,5]
  |_1       If falsy then -1     [-1,1,1,2,5]

Answer 11

Attache, 23 bytes

@{Max&-1!Divisors@_@-2}

Try it online!

29 bytes, pointfree: @(Max&-1@Last@ProperDivisors)

24 bytes, also pointfree: @(Max&-1@`@&-2@Divisors)

This simply gets the second-to-last divisor of n then takes the max of it and -1. The second-to-last element in an array with less than two elements is nil, and Max[-1, nil] is -1. @ simply vectorizes this function, making it apply to each atom.

Answer 12

Brachylog, 10 bytes

{fkt|∧_1}ˢ

Try it online!

The following explanation is mostly phrased imperatively for the sake of brevity, and does not accurately reflect Brachylog's declarative nature.

{          Start of inline predicate.
           Implicit input to the predicate.
 f         Create a list of all of the input's factors (including itself).
  k        Remove the last item of this list so that it no longer contains the original number.
   t       Take the last item of the list with the last item removed.
           Implicitly unify the output with the aforementioned last item.
    |      If that failed, because one of the lists was empty...
     ∧     discarding the input, (there's probably some obvious reason ∨ won't work here but I don't know what it is)
      _1   unify the output with -1 instead.
        }  End of the inline predicate.
         ˢ For every item of the input, unify it with the predicate's input and get a list of the corresponding outputs.

I decided I'd learn Brachylog so I could have some fun with code golf while hoping to learn some of the behavior of actual Prolog through osmosis, and I'm really enjoying it so far, even if I'm not entirely sure how the execution control characters work.

Answer 13

Wolfram Language (Mathematica), 33 bytes

Divisors[#][[-2]]/._Part:>-1&/@#&

Try it online!

Answer 14

R + numbers, 88 79 bytes

Thanks to the comments for some advice mainly about how to make submissions.

function(y)sapply(y,function(x)"if"(x<2,-1,prod(numbers::primeFactors(x)[-1])))

Uses the product of all prime factors except the smallest one, and the fact that the product of elements of an empty vector is defined to be 1.

Try it online!

Answer 15

Stax, 14 13 bytes

ü±p╞Ö*«òτ♀╣â▀

Run and debug it

Explanation (unpacked):

m|fc%c{vsH1?}U? Full program, implicit input-parsing
m               Map
 |fc%c            Get factorisation and length of it (0 and 1 yield [])
      {     } ?   If length != 0:
       v            Decrement
           ?        If still != 0:
        sH            Last element of factorisation
           ?        Else:
          1           Push 1
              ?   Else:
             U      Push -1

Pseudocode inside map:

f = factorisation(i)
l = length(f)
if l:
    if --l:
        return f[-1]
    else:
        return 1
else:
    return -1

Answer 16

Pyth, 12 bytes

me+_1f!%dTSt

Try it here

Explanation

me+_1f!%dTSt
m            Q    For each number d in the (implicit) input...
          Std     ... get the range [1, ..., d - 1]...
     f!%dT        ... take the ones that are factors of d...
  +_1             ... prepend -1...
 e                ... and take the last.

Answer 17

J, 14 bytes

1(%0{q:,-)@>.]

Try it online!

For every number n take the maximum of (n,1) instead.
Append the negated number to the list of its prime factors (empty list for 1), and divide the number by the first item in the list.

Also 14 bytes

(%0{q:) ::_1"0

Try it online!

Divide every number by the first of its prime factors. 0 raises a domain error with q:, and we look for the 0th item in an empty list for 1 — that’s an error as well. For any number that errors, return −1.

Answer 18

Japt, 14 11 8 bytes

®/k v)ªÉ
®        // For each input number,
 /k v    // return the number divided by it's first prime factor,
     )ªÉ // or -1 if such a number doesn't exist (the previous result is NaN).

Try it online!

Shaved off those three pesky bytes thanks to Shaggy.

Answer 19

JavaScript (Node.js), 6155 bytes

-6 bytes thanks to @shaggy

_=>_.map(_=>eval('for(v=_/(d=_>>1);v!=~~v;v=_/--d);d'))

Try it online!

---

Explanation :

_ =>                                     // input i.e : the original array
    _.map(                               // map over all elements of the array
        eval('                           // eval a string
            for(v=_/(d=_>>1);            // set v = _ / _ >> 1 and set that to d
                v!=~~v;                  // and keep going until v !== floor(v)
                        v=_/d--);        // to _ / d again (d was changed)
                    d'                   // return d
            ))                           // end eval and map and function

This is still for old code haven't updated this.

ES5 friendly as well:

 const primeOrNot = function(input) { // the function with argument input
      return input.map(function(value) { // returns the array after mapping over them
           d = Math.floor(value * 0.5); // multiply each element by 0.5 and floor it 
           for(let v = value / d; v != Math.floor(v);) { // for loop goes until v!=~~v
                d --; // subtract one from d
                v = value / d; // set v again to value / d
           }
           return d; // return d
      })
 };

Answer 20

Bash + GNU utilities, 49

• 9 bytes saved thanks to @Cowsquack

factor|sed '/:$/c-1
/: \w+$/c1
s%: %/%
y/ /#/'|bc

Explanation

• factor reads input numbers from STDIN, one per line and outputs in the format <input number>: <space-separated list of prime factors (ascending)>
• sed processes this as follows:
  • /:$/c-1 The input numbers 0 and 1 have no prime factors and are replaced with -1
  • /: \w+$/c1 Numbers with one prime factor (themselves) are prime. Replace these with 1
  • s%: %/% Replace : with /. This builds an arithmetic expression to divide the (non-prime) input number by its smallest prime factor to give the largest factor
  • y/ /#/ Remove the list of other (unneeded) factors (by commenting out)
• bc Arithmetically evaluate and display

Try it online!

Answer 21

Python 2, 61 59 bytes

lambda x:[max(k for k in[-1]+range(1,n)if n%k<1)for n in x]

Try it online!

---

Improvements

• 61 to 59 bytes by Dennis.

Answer 22

JavaScript (Node.js), 37 bytes

x=>x.map(a=>(f=t=>a%--t<1?t:f(t))(a))

Try it online!

Recursive, stack overflow for large input

JavaScript (Node.js), 41 bytes

x=>x.map(a=>eval('for(t=a;a%--t!=0;);t'))

Try it online!

Answer 23

Pari/GP, 37 bytes

a->[if(x<2,-1,x/divisors(x)[2])|x<-a]

Try it online!

Answer 24

Racket, 105 bytes

(λ(L)(map(λ(n)(if(< n 2)-1(p n(- n 1))))L))(define(p n d)(if(= d 1)1(if(=(modulo n d)0)d(p n(- d 1)))))

Try it online!

Answer 25

Befunge-98 (FBBI), 39 bytes

j&:!+f0p1-1:::' -:!j;3k$.nbj;-\%!!j:1+a

Try it online!

Ends with the & when there are no more numbers. This causes the program to stall for 60 seconds until TIO ends the program. This is unavoidable for Befunge-98, at least on TIO because both interpreters do this. After hitting play, you can stop the program after a bit in order to see what would be output if you did wait the minute.

---

Essentially, for every new number, if it is 0, it turns it into a 1. Then it puts a -1 onto the stack followed by a number that starts from 1 and counts up until it reaches the input number, in which case it prints out the second number on the stack (-1 for an input of 0 or 1, and the highest factor for others). Every time through the loop, we add the value of the iterator to the stack behind it if (input % iterator == 0). This means that when we get to the input, we just have to throw away the iterator and print. Then, we clear the stack with n and return to the read input function.

I may expand of the explanation later, we'll see...

Answer 26

Retina 0.8.2, 33 bytes

%(`^0|^1$
-1
\d+
$*
^(1+)\1+$
$.1

Try it online! Link includes those test cases that aren't too slow. Explanation:

%(`

Loop over each input number.

^0|^1$
-1

Special-case 0 and 1.

\d+
$*

Convert to unary (doesn't affect -1).

^(1+)\1+$
$.1

Replace each number with its largest proper factor in decimal.

Answer 27

tinylisp, 75 bytes

(load library
(q((L)(map(q((N)(i(l N 2)(- 1)(/ N(min(prime-factors N))))))L

Try it online! (Contains 4 extra bytes to give the anonymous function a name so we can call it in the footer.)

Ungolfed/explanation

Observe that returning 1 for prime \$n\$ and the largest factor less than \$n\$ for composite \$n\$ can be combined into returning \$n/p\$ where \$p\$ is the smallest prime factor of \$n\$.

(load library)               Library gives us map, -, /, min, and prime-factors functions

(lambda (L)                  Anonymous function, takes a list of numbers L
 (map                         Map
  (lambda (N)                  Anonymous function, takes a number N
   (if (less? N 2)              If N < 2
    (- 1)                        -1; else
    (/ N                         N divided by
     (min                        the minimum
      (prime-factors N)))))      of the prime factors of N
  L)))                        ... to L