Welcome to the 1st week of many challenges to come!
Problem
Find the smallest prime factor given n.
Example
factor(75) = 5 * 5 * 3, so the result would be 3.
Goal
Code Golf!
Language
Java
How to submit
The method needs to be in a class that also has the main method (basically just needs to take the first argument from the main method and output the result). Also include both golf’ed and non-gold’ed versions.
Funny, I wrote something with the capabilities to do just what your asking for a while ago… Maybe I can dig it out of the mountain of files hiding in my computer, needle in a haystack…
public class Challenge1 {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
float i = 2;
while (true) {
double d = n / i;
if (d == (int) d) {
System.out.println("Lowest prime = " + (int) i);
System.exit(0);
}
i++;
}
}
}
I’ve got a different way using the modulus operator.
public class Challenge1 {
public static void main(String[] a) {
int n = Integer.parseInt(a[0]);
for (int i = 2; i <= Math.abs(n); i++) {
if (n % i == 0) {
System.out.println("Lowest factor = " + i);
return;
}
}
System.out.println(n + " can only have itself as a factor."); // not strictly true, but go with it for the purposes of this.
}
}
Edit: After I posted, I realised you hadn’t said what the lower bound on the input is (originally assumed 2 by me), so I’ve assumed that you mean the lowest positive integer factor and caught edge cases. Otherwise, I could have been crafty and just said “-n”.
While I agree with you - it is Code Golf! It just adds valuable bytes to the program. Of course, I say that, I didn’t make a huge effort to minimise the number of bytes!
There are a couple of other optimisations you could do, for example, rather than going up in ones, you should just check the odd numbers after checking if the number is even or odd.
But doing sqrt() once is better than checking a hundred billion unnecessary values of i. Big-O and all that
What dual says is true, though. It does add valuable bytes. Makes me think that a variation of Code Golf where minimising runtime is the goal could be cool.
I combined some of the suggested performance improvements with @simon816’s algorithm since it was the fastest and came up with this. It’s a lot faster than anything else that’s been suggested (tested), only checks odds up to the square root of n.
public class Main {
public static void main(String[] args) {
System.out.println("Lowest Prime: " + lowestPrime(Integer.parseInt(args[0])));
}
public static int lowestPrime(int n) {
double two = n / 2F;
if (two == (int) two) return 2;
float i = 3;
double sqrt = Math.sqrt(n);
while (i <= sqrt) {
double divide = n / i;
if (divide == (int) divide) {
return (int) i;
}
i += 2;
}
return n;
}
}
Fast inverse sqrt relies on a magic number as well as pointer bitwise manipulation in regards to float and long types. You can read up more on it. Its not really on topic so no need for further explanation.
also lol at a few of these answers. There’s literally not much you can do in regards to reducing code if you’re limited to just java. Sure there’s obvious different ways of achieving the same goal.
Was bored so here’s my solution.
def main(args: Array[String]): Unit = {
val testNumbers = Array[Int](75, 89, 50, 142)
testNumbers foreach { x => println(x.toDouble <<<)}
}
implicit class <<<>>>(x: Double) {
def >>>(i: Int)(implicit d: Double = x / i) = d == d.floor
def <<< = (2 to x.toInt) find { x >>> }
}
edit: removed the Numeric generic type. For this usage it’s kinda stupid. As it’d be more work dealing with unintended types.
public class Challenge1 {
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
long factor = 1;
while (n % ++factor > 0);
System.out.print("Lowest prime factor: ");
System.out.println(Long.toString(factor));
}
}
Here’s the shortest way I can think of (107 characters)
class C{public static void main(String[]a){int f=1;while(Long.parseLong(a[0])%++f>0);System.out.print(f);}}
Note that neither classes have been tested to compile or run correctly, but in theory they should.