Welcome to DU! The truly grassroots left-of-center political community where regular people, not algorithms, drive the discussions and set the standards. Join the community: Create a free account Support DU (and get rid of ads!): Become a Star Member Latest Breaking News Editorials & Other Articles General Discussion The DU Lounge All Forums Issue Forums Culture Forums Alliance Forums Region Forums Support Forums Help & Search

eppur_se_muova

(38,541 posts)
2. "If you find a number like 1037615213 and you will find it to be extremely challenging."
Tue Dec 31, 2024, 04:23 AM
Dec 31
GP/PARI CALCULATOR Version 2.11.1 (released)
i386 running darwin (x86-64/GMP-6.0.0 kernel) 64-bit version
compiled: Nov 21 2018, Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
threading engine: single
(readline v6.3 enabled, extended help enabled)

Copyright (C) 2000-2018 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, q to quit.
Type ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? factor(1037615213)
%1 =
[ 17 1]

[ 19 1]

[3212431 1]

?


That wasn't so challenging. 17*19*3212431=1037615213 -- not just a single factor found, but a *complete* prime factorization. Took very much less than one eyeblink.

Apparently, you don't have much idea of how much work has been done in the field of factorization. It looks like your "algorithm" just generates a list of trial factors, then tries to divide by each one. Any randomly generated list should do at least as well. Of course, there are *lots* of better ways to do it than that, and any good book on number theory will list several approaches. Good old trial factoring is perfectly adequate in this case, since SQRT(1037615213) = 32212.0352... and there aren't that many numbers below 32213. Trying each number between 2 and 32212 in turn would show that there are no small factors besides 17 and 19, hence the remaining factor must be prime, and prime factorization is complete. This algorithm is made even faster by trying only *primes* below 33213, of which there are only ~4850 (by the Prime Number Theorem; an exact number can be found by an inclusion-exclusion algorithm).

I'm afraid your method "works" only in the sense that a broken clock is right twice a day.

BTW, no one uses division to test factors. It's too slow and inefficient. Use modular arithmetic -- the larger the numbers you're working with, the greater the advantage. Also, if your candidates may be composite numbers, you should find the Greatest Common Divisor (GCD) rather then just checking for even division.

Politely as I can put it -- please don't waste any more of your time, or further posts, on this topic without doing a LOT of reading in number theory first. I've included links to Wikipedia articles on various topics, but there are many more you could benefit from, if you're serious about really accomplishing something, rather than just trying things at random.

Recommendations

2 members have recommended this reply (displayed in chronological order):

Latest Discussions»Culture Forums»Science»Q_NLN_Factoring - an exte...»Reply #2