We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I actually did that overkill (even though we are limited to ints instead of even longs).
public int divisorSum (int N){
HashMap<Integer,Integer> primeFactorization = factor(N);
int total = 1;
for (int p:primeFactorization.keySet()) {
System.err.println("considering prime: " +p + " with mult: "+ primeFactorization.get(p));
int factor = 1;
for (int i=0;i<primeFactorization.get(p);i++) {
factor*=p;
factor+=1;
}
total*=factor;
}
return total;
}
private HashMap<Integer,Integer> factor(int n){
HashMap<Integer,Integer> mii = new HashMap<>();
if(isPrime(n)){
mii.put(n,1);
return mii;
}
if (n%2==0){
int m = n;
int cnt=0;
do{
m/=2;
cnt++;
}while(m%2==0);
mii.put(2,cnt);
}
double ceil = n/2.0;
for (int i = 3; i <= ceil; i += 2) {
if ((isPrime(i)) && (n%i == 0)) {
int m = n;
int cnt=0;
do{
m/=i;
cnt++;
}while(m%i==0);
mii.put(i,cnt);
}
}
return mii;
}
private static boolean isPrime(int num) {
if (num < 2) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i * i <= num; i += 2)
if (num % i == 0) return false;
return true;
}
No. Not understanding basic software engineering principles has nothing to do with sophistication. Premature optimization is the root of all evil. In the absence of measured performance issues, any optimization is a HUGE waste of time and a potential bug source. How long did it take you to write your solution? Mine was done in less than a minute. Welcome to real life programming. ;^)
I've been a programmer in real life for the past couple if decades., so I don't feel unqualified to respond to you here. Congratulations on your answer. However, dense one liners have a faTal flaw in the real world, they are not maintainable. Someone else, or even just you, has to come back and be able to Understand it, and to change Whatever the parts that go into it. For much the same reasons that premature optimization is the root of all evil, subpar clarity is too. It's better to waste white space than to over optimize or Over-stream.
You can't control the time budget that some future programmer is going to have when they come back to your code, and while streamed solutions are notoriously legible, they are very often equally immutable.
It's true, some people spend too much time overoptimizing something that doesn't matter in a particular application. In this case, with the constraint 1<=n<=1000, a simple brute force, especially when you stop at n/2, works very well.
However, if I'm programming something that I know is to be used in a more general fashion, the performance implications here are huge. The code above dramatically reduces the time needed, as the brute force method is very inefficient (particularly for a large n).
You may use wheel factorization and the divisor function. It is a bit tricky, but the resulting code is not too much complicated (just two cycles). Implementing the sieve, you have not to test if the divisor is actually prime.
Day 19: Interfaces
You are viewing a single comment's thread. Return to all comments →
I found a more efficient implementation here for those performance geeks. (Prime factorization is even better, but probably overkill.)
Note: Linked answer is slightly wrong, looks like they forgot to add the number itself to the sum. But you get the idea.
I actually did that overkill (even though we are limited to ints instead of even longs).
What the heck? :D See my solution, this is a one liner even in Java.
I invite you to read what I responded to because it wasn't just any simple attempt to solve the problem
It's a one liner if you're willing to do a brute force solution. Efficient solutions tend to be more sophisticated.
No. Not understanding basic software engineering principles has nothing to do with sophistication. Premature optimization is the root of all evil. In the absence of measured performance issues, any optimization is a HUGE waste of time and a potential bug source. How long did it take you to write your solution? Mine was done in less than a minute. Welcome to real life programming. ;^)
I've been a programmer in real life for the past couple if decades., so I don't feel unqualified to respond to you here. Congratulations on your answer. However, dense one liners have a faTal flaw in the real world, they are not maintainable. Someone else, or even just you, has to come back and be able to Understand it, and to change Whatever the parts that go into it. For much the same reasons that premature optimization is the root of all evil, subpar clarity is too. It's better to waste white space than to over optimize or Over-stream.
You can't control the time budget that some future programmer is going to have when they come back to your code, and while streamed solutions are notoriously legible, they are very often equally immutable.
I have no real life programming experience, so thank you for your debate, it was at least interesting for me.
It's true, some people spend too much time overoptimizing something that doesn't matter in a particular application. In this case, with the constraint 1<=n<=1000, a simple brute force, especially when you stop at n/2, works very well.
However, if I'm programming something that I know is to be used in a more general fashion, the performance implications here are huge. The code above dramatically reduces the time needed, as the brute force method is very inefficient (particularly for a large n).
sieve of eratosthenes !
You may use wheel factorization and the divisor function. It is a bit tricky, but the resulting code is not too much complicated (just two cycles). Implementing the sieve, you have not to test if the divisor is actually prime.