MHB Efficiency of Sieve vs. Derivative Method for Primality Testing

  • Thread starter Thread starter Hugo1177
  • Start date Start date
  • Tags Tags
    Formula Test
Click For Summary
The discussion centers on the efficiency of the sieve of Eratosthenes versus the derivative method for primality testing. Participants note that the modulo operation can determine if a number is prime, but there are questions regarding the computational efficiency of both methods, especially for large numbers. While one participant finds the sieve simpler and less time-consuming, there is uncertainty about whether it is indeed more efficient for larger primes compared to the derivative method. The conversation highlights a lack of consensus on the best approach, particularly regarding polynomial time efficiency. Ultimately, the effectiveness of each method remains debated among those without deep expertise in computational time.
Hugo1177
Messages
2
Reaction score
0
We can determinate if one number is prime with the modulo operation.
https://www.researchgate.net/publication/346647223_Primality_Test_Formula
 
Mathematics news on Phys.org
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
 

Similar threads

  • · Replies 96 ·
4
Replies
96
Views
11K
  • · Replies 16 ·
Replies
16
Views
3K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 6 ·
Replies
6
Views
5K
  • · Replies 29 ·
Replies
29
Views
5K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K