I’ve been working on this problem for a while as a relatively new student and just can’t seem to figure it out.
I’ve gotten the basic stuff down, dividing the factorials and displaying my result, however always go under the time limit.
I’ve found a couple of methods to shrink my run time by half, but I still can’t get past test #4.
This is my current code, however, I’ve realized it is very inefficient to calculate, per se, 5 million 1 million times individually if that was the given input. It would be easier to have all of the “numbers of factors” in an array or ArrayList, but can’t figure out how to implement this.
public static int primeFactorization(int n) {
int res=0;
for (int i=2;i <= Math.sqrt(n);i++) {
while (n % i == 0) {
res++;
n=n/i;
}
}
if (n > 1) {
res++;
}
return res;
}
What I’m looking for is to have an array with all of the numbers of factors for every number from 1 to 5,000,000, but my inexperience with dealing with array lists is stopping me.
Example:
[1,2,3,4,5…]
[0,1,1,2,1…]
with each term corresponding to the number of factors in that number (besides 1).
This is probably incredibly simple but I would appreciate any advice to tackle this. If you want, here is my entire program so far:
(the fastIO is copied from the fast input and output lesson)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
FastIO io = new FastIO();
int x = io.nextInt();
for (int i = 0; i <= x-1; i++) {
int a = io.nextInt();
int b = io.nextInt();
io.println(factorialDivision(a,b));
}
io.close();
}
public static int primeFactorization(int n) {
int res=0;
for (int i=2;i <= Math.sqrt(n);i++) {
while (n % i == 0) {
res++;
n=n/i;
}
}
if (n > 1) {
res++;
}
return res;
}
public static int factorialDivision(int m, int n) {
int a=0;
for (int i = m; i > n; i--) {
a+=primeFactorization(i);
}
return a;
}
}
class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
// standard input
public FastIO() { this(System.in, System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) { throw new InputMismatchException(); }
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) { throw new InputMismatchException(); }
if (numChars == -1) {
return -1; // end of file
}
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c;
do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = nextByte();
} while (c > ' ');
return res.toString();
}
public int nextInt() { // nextLong() would be implemented similarly
int c;
do { c = nextByte(); } while (c <= ' ');
int sgn = 1;
if (c == '-') {
sgn = -1;
c = nextByte();
}
int res = 0;
do {
if (c < '0' || c > '9') { throw new InputMismatchException(); }
res = 10 * res + c - '0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}