Prime factorization, Composite integers.

Question

Describe how to find a prime factor of 1742399 using at most 441 integer divisions and one square root.

So far I have only square rooted 1742399 to get 1319.9996. I have also tried to find a prime number that divides 1742399 exactly; I have tried up to 71 but had no luck. Surely there is an easier way that I am missing without trying numerous prime numbers. Any help would be great, thanks.

Answer 1

Note that the problem asks you do describe how you would go about factorizing 1742399 in at most 442 operations. You are not being asked to carry out all these operations yourself! I think your method of checking all primes up to the squareroot is exactly what the problem is looking for, but to be safe you should check that there are no more than 441 primes less than or equal to 1319.

Answer 2

Are you allowed to have a table of prime numbers? There are fewer than 441 such primes below 1320.

You probably aren't supposed to use this method, but 1742399 is nearly a square as you have identified and you can write it as 1742400-1, which is the difference of two squares. This gets you two smaller factors almost for free.

Answer 3

• you need only to test numbers up to $1319$.
• test $2$ for even numbers
• test $3$ for multiples of $3$
• the remaining numbers will be $1$ or $5 \bmod 6$

Answer 4

Hint $\ $ Prime $\rm\:p\neq 2,3\:\Rightarrow\: p\equiv \pm 1\pmod 6$

Remark $\ $ For more on sieving see my post here, which includes links to ingenenious mechanical sieving machines devised by Lehmer in the precomputer era, e.g. using bicycles chains, photoelectric devices, etc. Below are some general references.

Wooding, Kjell. The Sieve Problem in One and Two-Dimensions.
PhD Thesis. Calgary, Alberta. April, 2010

Lehmer, D.H. The sieve problem for all-purpose computers, MTAC, v. 7 1953, p. 6-14