Return to Question

Euler came up with following recurrence relation for the sum of divisors (refer to http://arxiv.org/abs/math/0411587) $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$

Since $\sigma(p) = p+1$, where $p$ is a prime number, we can use the recurrence relation to verify if a number is prime. I'm wondering how efficient it is to use this method to find a prime, or more specifically to build up all the primes up to a number. It seems pretty fast to add a few numbers, especially the numbers subtracted in the recurrence relation are increasing quadratically?

(I've also asked this question on math.stackexchange: http://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation)

Euler came up with following recurrence relation for the sum of divisors (refer to http://arxiv.org/abs/math/0411587) $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$

Since $\sigma(p) = p+1$, where $p$ is a prime number, we can use the recurrence relation to verify if a number is prime. I'm wondering how efficient it is to use this method to find a prime, or more specifically to build up all the primes up to a number. It seems pretty fast to add a few numbers, especially the numbers subtracted in the recurrence relation are increasing quadratically?

(I've also asked this question on math.stackexchange: https://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation)

Euler came up with following recurrence relation for the sum of divisors $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$

Since $\sigma(p) = p+1$, where $p$ is a prime number, we can use the recurrence relation to verify if a number is prime. I'm wondering how efficient it is to use this method to find a prime, or more specifically to build up all the primes up to a number. It seems pretty fast to add a few numbers, especially the numbers subtracted in the recurrence relation are increasing quadratically?

(I've also asked this question on math.stackexchange: http://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation)

Euler came up with following recurrence relation for the sum of divisors (refer to http://arxiv.org/abs/math/0411587) $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$

Since $\sigma(p) = p+1$, where $p$ is a prime number, we can use the recurrence relation to verify if a number is prime. I'm wondering how efficient it is to use this method to find a prime, or more specifically to build up all the primes up to a number. It seems pretty fast to add a few numbers, especially the numbers subtracted in the recurrence relation are increasing quadratically?

(I've also asked this question on math.stackexchange: http://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation)