Finding all divisors of a number

  • Context: High School 
  • Thread starter Thread starter ShayanJ
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around methods for finding all divisors of a number, exploring both basic and advanced techniques. Participants consider the efficiency of various approaches, including trial division and prime factorization, as well as more complex algorithms for larger numbers.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests that divisors can be found by dividing the number from 2 to its half.
  • Another participant counters that division only needs to go up to the square root of the number and can be limited to prime numbers.
  • A different viewpoint proposes that finding prime factors first is the easiest method to determine all divisors, mentioning trial division up to the square root.
  • Advanced methods such as Pollard's rho algorithm, elliptic curve factoring, and number field sieves are mentioned for factoring large numbers efficiently.
  • Concerns are raised about the clarity of the advanced methods, with requests for explanations and accessible resources.
  • Participants discuss the implications of finding factors greater than the square root and how that relates to identifying all divisors.
  • There is a reiteration of the importance of understanding the context of using only prime numbers for division.

Areas of Agreement / Disagreement

Participants express differing opinions on the best methods for finding divisors, with some advocating for trial division and others for prime factorization. There is no consensus on the clarity of the advanced methods mentioned, and some participants seek further explanation.

Contextual Notes

Some participants note the limitations of the explanations provided, particularly regarding the advanced factoring methods, which may not be easily accessible or understood without further detail.

Who May Find This Useful

This discussion may be useful for individuals interested in number theory, mathematical problem-solving, or those seeking efficient methods for divisor finding.

ShayanJ
Science Advisor
Insights Author
Messages
2,802
Reaction score
605
Good time people
Is there any way other than dividing the number from 2 to its half to find all of its divisors?
Anyway may help so feel free telling your ideas
thanks
 
Mathematics news on Phys.org
First of all you don't have to divide up to the number's half, only up to it square root. Second, you only have to divide by prime numbers.
 
It's easiest to first find all the prime factors of a number, and then determine the divisors from that list. Finding the prime factors requires only trial dividing up to the square root of the number -- and then only by the primes, if you like.

Methods like Pollard's rho algorithm, elliptic curve factoring, and the number field sieves can be used to factor large numbers (say, > 10^9) much more quickly.

Practically, if you don't recognize these terms, I recommend a tool like
http://www.alpertron.com.ar/ECM.HTM
 
Hello
Did you noticed 71,a prime factor of 284?
it is greater than 16.85 that is the square root of 284.
 
And one more thing...
Could you explain the methods you named?
the page you gave the link of,doesn't include a explanation about the method itself.
I searched it in the internet but i found no easy explanation.
thanks
 
Hi Shyan,

I had visited a site called eTutorWorld its online tuition site.
 
Shyan said:
Hello
Did you noticed 71,a prime factor of 284?
it is greater than 16.85 that is the square root of 284.

Yes, but 284=71*4. So by finding 4, you've found 71 as a factor also. If a> sqrt(n), and ab = n, then b<sqrt(n) necessarily.
 
Yes, but I think Shyan was referring to Skeptic2's advice to only go up to and only use prime numbers. 2 divides into 284 142 times but you don't immediately see the "71". Of course the intelligent thing to do once you have 284= 142 would be to ignore the 284 and start factoring 142 so that you immediately get 2*71 but it is not clear that was what Skeptic2 meant.
 
HallsofIvy said:
Yes, but I think Shyan was referring to Skeptic2's advice to only go up to and only use prime numbers. 2 divides into 284 142 times but you don't immediately see the "71". Of course the intelligent thing to do once you have 284= 142 would be to ignore the 284 and start factoring 142 so that you immediately get 2*71 but it is not clear that was what Skeptic2 meant.

Agreed.
 
  • #10
shyan said:
Could you explain the methods you named?
Please!
 

Similar threads

High School Problems in finding divisors using permutation,combination
  • · Replies 1 ·
Replies
1
Views
1K
High School Divide by 4 and multiply by 15
  • · Replies 14 ·
Replies
14
Views
2K
High School Are All Imaginable Integer Series Necessarily Infinite?
  • · Replies 17 ·
Replies
17
Views
2K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
High School Find Functions Satisfying $f^d(x)=2015-x$ for All Divisors of 2015
  • · Replies 1 ·
Replies
1
Views
2K
High School How to find large modulus on Casio fx-991 MS
  • · Replies 7 ·
Replies
7
Views
42K
Undergrad Is the equation 0!=1 based on flawed reasoning?
  • · Replies 55 ·
2
Replies
55
Views
7K
High School Is PI (##\pi##) really a number?
  • · Replies 28 ·
Replies
28
Views
3K
High School How to pick some numbers out of 13 integers, by a 4 digits code
  • · Replies 4 ·
Replies
4
Views
2K
High School Term for continuously halving a number
  • · Replies 7 ·
Replies
7
Views
3K