Message Boards Message Boards

GROUPS:

Why Divisors[ ] is far faster than Factorinteger[ ]?

Posted 9 days ago
171 Views
|
5 Replies
|
5 Total Likes
|

Hi there, anyone can tell me what are the codes behind the command "Divisors", how it is intrinsically done? I mean what is the algorithm behind it? does it use a command solve for the different modulus that equals zero as the remainder? Why is it not used to give a PrimeQ statement if it is so fast? I mean if there is only one divisor other than the number that is being divided itself isn't a prime? I am just curious about the logics behind this intriguing command...thank you anyway.

5 Replies

What makes you think that Divisors is faster than PrimeQ?

Perhaps it is faster for small number (103 or so).

But for large numbers PrimeQ is quite a bit faster than divisors (e.g. PrimeQ[418763839831824213]).

I am working with prime numbers I found a way for really huge numbers far faster than prime q, and I have checked against prime Q, it gives a right answer for seven out of 8 ... I am improving it ...just tried divisors and it works for numbers with 77 digits really fast I just wondered why divisors can not be improved so I wanted to know how it works in the core...thank you.

For many digits the validity of the prime-testing method is anyhow questionable. They are only valid (proven valid) up to some number.

Check also https://reference.wolfram.com/language/PrimalityProving/ref/PrimeQCertificate.html

Divisors is a kernel function:

Needs["GeneralUtilities`"]
PrintDefinitions[Divisors]

so only the developers can tell you really how it works internally…

Thank you so much Mr. Sander I will check it!!!

Is there a way to do what the command divisors[] do in a reverse manner instead of incrementing i++ the numbers that will be checked for the division with remainder 0 starting from a given number lets say 848576890394122387 to 0, the only problem I find to use divisors[] as a way to check for primality is that for large number with 10000000 digits it takes too long to reach the maximum divisor, since what I am trying to find are pseudoprimes with factors too high I should do the reverse, decrementing the numbers from a given number and checking for Mod[a,n]=0, I think it would be faster than primeQ that also works its way up....

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract