# [Challenge] Week #1 - Calculating Primes

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.

1 Like

Post results here, or email directly to your professor?

2 Likes

This isn’t an assignment for any classes or similar I have, it’s just for fun. I’ll be posting my own version soon.

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++;
}
}
}
``````
1 Like
``````public class Challenge1 {
public static void main(String[] args) {
int n;
try {
n = Integer.parseInt(args[0]);
} catch (NumberFormatException ignored) {
System.out.println("Invalid number. Try again.");
return;
}
float i = 2;
while (true) {
double d = n / 1;
if (d == (int) d) {
System.out.println("Lowest prime = " + (int) i);
return;
}
i++;
}
}
}
``````

Effectively the same method as @simon816, but I like displaying the differences in code style, sometimes.

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”.

Can I be the math guy and say that y’all only need to check up to int(sqrt(n))+1 (Python syntax, sorry)? Think run-time for large primes, guys!

Square Rooting is one of the more intensive math calculations you can do.

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.

What about Fast inverse square root - Wikipedia?

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;
}
}``````
2 Likes

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.

Thats the reason why is java extremly bad language for codegolf games. Java has simply too much syntactic sugar

• perl, ruby, c, lisp, golfscript are more interesting choices.

109 Characters

``````class M{public static void main(String[]a){int i=1;while(Integer.valueOf(a[0])%++i!=0);System.out.print(i);}}
``````

With white space:

``````class M {
public static void main(String[] a) {
int i=1;
while(Integer.valueOf(a[0]) % ++i != 0);
System.out.print(i);
}
}
``````

Edit: Using some of the optimizations used by CrazyPyroEagle I get 105 characters.

``````class M{public static void main(String[]a){int i=1;while(Long.valueOf(a[0])%++i>0);System.out.print(i);}}
``````
1 Like

Here’s the fastest way of doing it I can think of

``````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.

Wow! I did not knew you can omit the space between `String[]` and `a`

``````double d = n / 1;
``double d = n / i;``