I m solving a problem to find the sum of divisors of a given number(the number is a large one),...i hv written the code bt it's exceding the time limit...hw can i reduce the time in such cases...pls help me....i m a beginner 2 programming in c :)
Hre is my code:
#include<stdio. h>
int main()
{
long long int k,n,t,sum=0;
scanf("%lld",&t );
while(t)
{
scanf("%lld",&n );
for(k=1;k<n;k++ )
{
if(n%k==0)
{
sum=sum+k;
}
}
printf("%lld\n" ,sum);
t;
sum=0;
}
system("pause") ;
return 0;
}
15 20645 YarrOfDoom 1,247
Recognized Expert Top Contributor
There's a lot of numbers you can easily skip here, you just have to think about the maths behind it.
Think about this for instance: "What's the highest divisor I'm ever going to find for a number (excluding the number itself of course)?"
If you can calculate this number (or an approximation of it) before the loop, you only have to go up to this number, instead of all the way up to the given number.
I'm sure if you look into it a little bit further you can find other ways to speed it up as well.
PS: If you post your code in codetags (put [code] in front of your code and [/code] behind it), it is much easier to read for everyone. More posting guidelines can be found here.
donbock 2,426
Recognized Expert Top Contributor
Remember that divisors come in pairs. Every time you find a divisor with your loop you can then find its partner. Then your loop only needs to find half the divisors.
@yaarofdoom
Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help
@donbock
Thanks can u suggest a better algorithm for this 1??
@yaarofdoom
Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help
@donbock
Thanks can u suggest a better algorithm for this 1??
...i dis forum,ill tk care abt it
There are 3 words I understand (forum, care, it) and 5 that I either don't know or that look misplaced in this context ( 'i' and 'ill'). Maybe it's not that important, though.
I'd find all prime factos of the number in question ( with their respective powers) and then compute all possible divisors from them. ( if n = p_1^k_1 * ... * p_n^k_n , you have (k_1+1)*...*(k_ n+1) possible divisors.
@yaarofdoom
Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help
@donbock
Thanks can u suggest a better algorithm for this 1??
@yaarofdoom
Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help
@donbock
Thanks can u suggest a better algorithm for this 1??
YarrOfDoom 1,247
Recognized Expert Top Contributor
Could you please stop copypasting the same post over and over again?
How about you show some of the efforts you have done yourself to implement the suggestions we have given you, so we can help you on that?
And putting some more effort into your spelling would be greatly appreciated as well (maybe you should read the posting guidelines again).
donbock 2,426
Recognized Expert Top Contributor
As you said, you could limit your search for divisors to the range from 1 to n/2. However, you can do even better. Consider your divisor search ... you start with 1 and find its partner (n), then find the next divisor (i) and its partner (n/i). Notice that the partners are larger than the initial divisors: n > 1, n/i > i, etc. As your divisors increase the partners decrease. You continue looking for divisors until the partner is less than or equal to the divisor. After that, all you're doing is finding another instance of a pair you already found.
So ... the trick for deciding when to look for divisors is when the partner is less than or equal to the divisor. Think about the arithmetic for awhile  how can you characterize this transition point?
Sign in to post your reply or Sign up for a free account.
Similar topics 
by: andrea.gavana 
last post by:
Hello NG,
I was wondering if there is a faster/nicer method (than a for loop)
that will allow me to find the elements (AND their indices) in a list that
verify a certain condition. For example, assuming that I have a list like:
mylist =
I would like to find the indices of the elements in the list that are equal
to 1 (in this case, the 1,2,3,4,9 elements are equal to 1). I could easily

by: Philp Smith 
last post by:
Hi
Does anyone have suggested code for a compact, efficient, elegant, most of
all pythonic routine to produce a list of all the proper divisors of an
integer (given a list of prime factors/powers)

by: Sriram Krishnan [at] gmx [dot] net 
last post by:
Given an arbitrary number series, how do I identify the series and find the
Nth number...
for e.g 1,3,5,7 is an AP and the next number will be 9
1,8,27,64 is the series of cubes and the next will be 125
1,1,2,3,5,8 is the Fibonacci series
The thing is I'll be given the series only...I have to identify the series
and find the next number. Pointers on how to do this please ...
Regards,
Sriram

by: J. B. Moreno 
last post by:
What's the best (i.e. fastest) way to find out if an array contains a given
value? Other than looping, the only way I know to do it is to use an
associative array/hash instead....
Is there a better/faster way?
I.e if I have a list of names, what's the best way to find out if the aray
contains "jane"?


by: shafique 
last post by:
Hello,
Can anybody have idea as how to find it there exist consective one's in
a word/dword using bitwise operatiors in C language.
Obviously this can be done by shifting and looping one by one; but
there must be some faster way of doing it.
The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword. e.g. 0000b has no consective
 
by: Jozef Jarosciak 
last post by:
Quickest way to find the string in 1 dimensional string array!
I have a queue 1 dimensional array of strings called 'queue' and I need
a fast way to search it. Once there is match, I don't need to search
any longer.
Currently I am using this code.
But I think it's too slow, because it runs through whole dimension.
I know this is trivial question, but is there any way to stop this
loop, or better way to search? I mean  FASTER?

by: Imran 
last post by:
I have a vector of integers, such as
and I want to find out the number which occurs most frequently.what is the
quick method. My array size is huge.
what I am doing is
1. find out the maximum value N
2. loop through 1...N
3. count # times each occurred

by: Clint Boaz 
last post by:
I am just trying to learn C++ and having a problem trying to write a program that finds the sum of the proper divisors of a given integer n and returns whether n is deficient, perfect or abundant.

by: \A_Michigan_User\ 
last post by:
I call this Javascript function with "GetEleNum(this)"
passing it 1 of the elements of a textbox array.
Is there a QUICK way to get the "element #"? I'm currently using this
SLOW code.
(It works... but I need something better/faster.)
function GetEleNum(c)
{
// Given 1 element in this textBox array... what is the array element #?

by: jimix 
last post by:
I have written the program for factors of #'s 150 but the factors print out below the number being factored. I can't figure out how to make it all on the same line.
i.e. (now) divisors of 25 are
1
5
25
(need) divisors of 25 are 1, 5, 25.
here is my code;
#include <stdio.h>

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
 
by: Hystou 
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...

by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++12 std=c++20 Wnarrowing bit_field.cpp
Here is the code in...

by: Hystou 
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...

by: TSSRALBI 
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LANtoLAN VPNs.
The last exercise I practiced was to create a LANtoLAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
 
by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.

by: bsmnconsultancy 
last post by:
In today's digital era, a welldesigned website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
 