Follow us on Twitter!
It is never to LATE to become what you never WERE.
Sunday, April 20, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 32
Guests Online: 30
Members Online: 2

Registered Members: 82850
Newest Member: hardstylurr
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming

Author

program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 08:55
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 x04; N x04; 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"Wink;
else
printf("%ld\n",mul);
}
//getch();
}


thanx for reading....
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 14:54
This is the wrong site to ask, most people will just say piss of and learn yourself.

Try to use google it will probably give you a better answers or ask on a site dedicated to help people with programming.
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 16:13
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.
Code

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++)

Code

#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

Code

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).
Author

RE: program optimization...

spyware
Member



Posts: 4192
Location: The Netherlands
Joined: 14.04.07
Rank:
God
Warn Level: 90
Posted on 04-06-09 16:32
Homework thread.

Wheeeeeeee.



img507.imageshack.us/img507/3580/spynewsig3il1.png
"The chowner of property." - Zeph
[small]
Widespread intellectual and moral docility may be convenient for leaders in the short term,
but it is suicidal for nations in the long term.
- Carl Sagan
“Since the grid is inescapable, what were the earlier lasers about? Does the corridor have a sense of humor?” - Ebert
[/s
http://bitsofspy.net
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 18:59
spyware wrote:
Homework thread.

Wheeeeeeee.


Indeed, that was my first thought as well.


Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 23:16
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.
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 23:49
go to your teacher if you cant solve it
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 04-06-09 23:57
1337h4cker wrote:
go to your teacher if you cant solve it


depends on the teacher... sometimes they're ass holes.
Author

RE: program optimization...


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 05-06-09 01:11
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.


Author

RE: program optimization...

fashizzlepop
Member



Posts: 482
Location: Old folks home.
Joined: 08.04.08
Rank:
Moderate
Posted on 05-06-09 02:22
shivmitra wrote:
given a number N, compute the product of its positive divisors.


You might want to re-read your problem first. Saved your grade.


"The definition of insanity is doing the same thing over and over again and expecting different results.”
~Albert Einstein~


csullivan.codeinspire.net/images/boomsig2.png
fashizzlepop@gmail.com http://csullivan.codeinspire.net/