program optimization...
Being in love with number theory, Johnny decided to take a number theory course. On the first day, he was challenged by his teacher with the following problem: given a number N, compute the product of its positive divisors. Johnny is desperate to impress his new teacher so he asks you for help.
In this problem, the divisors of N do not include the number N itself. For example, if N=12, the divisors of N (excluding N) are 1, 2, 3, 4, and 6. Thus, the product of divisors is 1x2x3x4x6=144. Since the result may be very large, if the result has more than 4 decimal digits, Johnny only needs to compute the last 4 digits of it. Input
The first line contains t, the number of test cases (about 300,000). Then t test cases follow.
Each test case contains a single integer N (2 ≤ N ≤ 500,000) whose product of divisors needs to be computed. Output
For each test case, print a single line containing the corresponding result of that test case. Example
Input 6 3 4 12 25 957 10000
Output 1 2 144 5 7493 0000
Date: 2009-05-05 Time limit: 2s Source limit: 50000B Languages: All
i hav written code using brute forcing approach.but time limit of 2s exceeds.hw can i reduce time limit.Tell me if my approach is wrong… my code is below-
#include<stdio.h> //#include<conio.h>
int main() { register long int t; scanf("%d",&t); for(register long int y=0;y<t;y++) { long int mul=1; long int n; int x=0; scanf("%ld",&n); for(register long int i=2;i<=n/2;i++) { if(n%i==0) { mul=mul*i; if((mul/10000)!=0) { mul=mul%10000; x=1; } } } if(x==1 && mul==0) printf("0000\n"); else printf("%ld\n",mul); } //getch(); }
thanx for reading….
Well for one, you dont have to iterate the loop all the way until you reach N. You can safely stop at N/2 because usually the last or largest factor (excluding N) comes before or right at N/2. And if you have to get N included as a factor, you can just multiply the product of your divisors by N as a separate step.
You could make a chart to prove it.
N..........N/2..........Largest factor (excluding N)
6...........3............3
8...........4............4
9.........4.5...........3
10.........5............5
12.........6............6
14.........7............7
...etc
I whipped up a little bit of code and noticed at 25, you got 5. Are you not supposed to list factors that occur more than once? I'm rusty and haven't coded in a while, but here's what I have (in C++)
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
//get number
int number;
unsigned long int productofdivisors=1;
cin>>number;
for(int i=1;i<=(number/2);i++){
/*I did number/2 because i noticed usually after half the number i reached, there are no more factors except for whatever the number is itself.*/
if(number%i==0){
productofdivisors*=i;
}
}
cout<<productofdivisors;
getch();
return 0;
}
Replacing the contents of the for loop with
if(sqrt(number)==i){
productofdivisors*=(i*i);
}
else{
productofdivisors*=i;
}
catches cases where a factor occurs more than once in a number like 25 (where 5 occurs twice).
styloverte116 wrote: you don't have to go to N/2. only the square root of N, cause youll already have figured out the higher divisors by doing N/lowerDivisor.
spy and caps… hes learning… hw isnt always best done by yourself. he provided code.. of which i didnt look at but im sure he put some effort in.
All too true, I'm embarassed that I knew that but didn't think of it.