Message Boards Message Boards

1
|
3537 Views
|
5 Replies
|
5 Total Likes
View groups...
Share
Share this post:

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

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

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....

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…

POSTED BY: Sander Huisman

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

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]).

POSTED BY: Sander Huisman
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