1
$\begingroup$

Let's say I have a list of random numbers, all very big;

$$A: 1304810398401344441324$$

$$B: 5641893748137481374813764$$

$$C: 33322299992418948194899999$$

etc..

I want to be able to divide each and every number with another number, let's call it a divider, which will be unique for each number, however, I would like to find the biggest "divider" which will divide a number without leaving fractions.

How can I go about doing this in an efficient manner without trying every possible combination of random numbers???

to make it less complicated I'm making the "divider" at least $\frac 13$ as long as the number that's being divided by it.

Is this possible at all?

Thanks.

$\endgroup$
  • $\begingroup$ Look up integer factorization $\endgroup$ – Robert Israel Mar 28 '18 at 17:33
  • $\begingroup$ Find the prime factorization of each number, and then find what factors (and to what power) they all have in common. P.s. the three numbers you just listed there do not share any common divisor. $\endgroup$ – Bram28 Mar 28 '18 at 17:33
  • $\begingroup$ What you call "dividers" are usually called "divisors", Of course, any number is its own larger divisor. If I understand the question correct, you are looking for how to determine the "largest proper divisor" of a given integer. (Here proper means that you exclude the given nubmer itself.) $\endgroup$ – Travis Willse Mar 28 '18 at 17:37
  • $\begingroup$ Oh I think I made it unclear, I meant each number will have a unique divisor, which will make it as small as possible. $\endgroup$ – ABOODYFJ Mar 28 '18 at 17:39
  • $\begingroup$ @Travis yes that's what I'm trying to do $\endgroup$ – ABOODYFJ Mar 28 '18 at 17:39
2
$\begingroup$

A thorough answer to your question is impossible on this site. Whether one can factor large numbers efficiently is an important open question. If you could do it much of the security on the internet would be at risk.

Your examples aren't particularly large for fast computers using the most efficient algorithms known. Wolfram alpha does the first one pretty much instantaneously, yielding $$ 1304810398401344441324 = 2^2×47×6940480842560342773 $$ https://www.wolframalpha.com/input/?i=factor+1304810398401344441324

You can start reading at

https://en.wikipedia.org/wiki/Integer_factorization

$\endgroup$
-1
$\begingroup$

Just divide each $n$ by $n$ itself (or $n/2)$. That trivially satisfies all your stated requirements.

$\endgroup$
  • $\begingroup$ unfortunately not, the number itself must be reduced in size as an outcome. And not to 1, 5000 to 50*100 is an example for what I need to acheive. $\endgroup$ – ABOODYFJ Mar 28 '18 at 18:16
  • $\begingroup$ The question does say "another number" to be fair; implying distinctness. $\endgroup$ – samerivertwice Mar 28 '18 at 19:41
  • $\begingroup$ OK. Then just divide $n$ by $n/2$. Somehow I have a feeling the OP simply hasn't stated the true question at hand. $\endgroup$ – David G. Stork Mar 28 '18 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.