Efficiency of Sieve vs. Derivative Method for Primality Testing

• MHB
• Hugo1177
In summary, the conversation discusses different methods for determining if a number is prime, including the use of the modulo operation and the sieve of Erastothenes. The efficiency of these methods is also discussed, with the suggestion that the sieve may be simpler and less time consuming. The conversation ends with a note about the potential limitations of these methods and the possibility of being wrong in their assumptions.
Hugo1177
We can determinate if one number is prime with the modulo operation.
https://www.researchgate.net/publication/346647223_Primality_Test_Formula

Hugo1177 said:
We can determinate if one number is prime with the modulo operation.
https://www.researchgate.net/publication/346647223_Primality_Test_Formula
Interesting. However I find the usual sieve of Erastothenes to be simpler and less time consuming. (I believe that the two methods are related to each other anyway.)

-Dan

I am not an expert in computational time, are you sure that the sieve is better for big numbers? I hear that there aren´t a efficient form to determinate if a number is prime or not in polynomial time. Here you only have to do the 30th or 40th derivative and divide one number relatively big by other

Hugo1177 said:
I am not an expert in computational time, are you sure that the sieve is better for big numbers? I hear that there aren´t a efficient form to determinate if a number is prime or not in polynomial time. Here you only have to do the 30th or 40th derivative and divide one number relatively big by other
I'm not an expert either. I'm simply guessing that taking derivatives is more time consuming than doing the sieve. I admit I may be wrong.

-Dan

What is a primality test formula?

A primality test formula is a mathematical equation used to determine if a given number is prime or not. It is a crucial tool in number theory and is used to identify prime numbers, which are numbers that can only be divided by 1 and themselves.

Why do we need primality test formulas?

We need primality test formulas because prime numbers are important in various fields, such as cryptography, computer science, and mathematics. They are also used in the generation of random numbers, which are essential in many applications. Primality test formulas help us efficiently identify prime numbers without having to manually check every possible factor.

What are some commonly used primality test formulas?

Some commonly used primality test formulas include the Sieve of Eratosthenes, Fermat's Little Theorem, and the Miller-Rabin test. Each formula has its own advantages and limitations, and they are used in different scenarios depending on the size of the number being tested and the level of accuracy required.

Are primality test formulas always accurate?

No, primality test formulas are not always accurate. Some formulas, such as the Fermat's Little Theorem, have a small chance of producing a false positive result. This means that the number is identified as prime, but it is actually composite. However, these chances can be reduced by using multiple primality test formulas in combination.

Can primality test formulas be used for very large numbers?

Yes, primality test formulas can be used for very large numbers. However, as the size of the number increases, the complexity and time required to perform the test also increase. This is why more efficient and advanced primality test algorithms are constantly being developed to handle larger numbers in a shorter amount of time.

• General Math
Replies
1
Views
961
• General Math
Replies
7
Views
1K
• General Math
Replies
96
Views
10K
• General Math
Replies
16
Views
3K
• Electrical Engineering
Replies
4
Views
437
• General Math
Replies
14
Views
1K
• General Math
Replies
3
Views
1K
• General Math
Replies
1
Views
780
• General Math
Replies
9
Views
2K
• Materials and Chemical Engineering
Replies
1
Views
1K