Formula for primes: Difference between revisions

Revision as of 09:30, 24 May 2009

Revision as of 09:51, 24 May 2009

Line 96:

:<math>\pi(k) =1 + \sum_{j=2}^k 1+\left\lfloor {-1 + {2 \over j} \left(1 - \sum_{s=12}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) \right)\right\rfloor </math>

Line 106:

\end{cases} </math>

:<math>\sum_{s=12}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) = \begintext{casesnumber of divisors of j} </math>

1 & \text{s divides j} \\

:<math>\left\lfloor {-1 \over j} \left(\sum_{s=2}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) \right)\right\rfloor=\begin{cases}

0 & \text{s does not divide j}

0 & \text{j is prime} \\

\end{cases} </math>

-1 & \text{j is composite}

\end{cases} </math>

:<math>IsPrime(x)=1+\left\lfloor {-1 \over j} \left(\sum_{s=2}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j \over s}\right\rfloor - \left\lfloor{j-1 \over s}\right\rfloor\right) \right)\right\rfloor=\begin{cases}

1 & \text{sj dividesis jprime} \\

0 & \text{sj doesis not divide jcomposite}

\end{cases}</math>

:<math>\pi(k) =\sum_{j=2}^k IsPrime(j) </math>

===Converting primality tests to prime number formulas===