SHARE
TWEET

Sieve of Eratosthenes by odd numbers

Bodigrim Nov 20th, 2011 5,643 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function sieve2(n){
  2.         S = [];
  3.         // заполняем решето единицами
  4.         for(k=1; k<=n; k++)
  5.                 S[k]=1;
  6.        
  7.         for(k=1; (2*k+1)*(2*k+1)<=2*n+1; k++){
  8.                 // если 2k+1 - простое (т. е. k не вычеркнуто)
  9.                 if(S[k]==1){
  10.                         // то вычеркнем кратные 2k+1
  11.                         for(l=3*k+1; l<=n; l+=2*k+1){
  12.                                 S[l]=0;
  13.                                 }
  14.                         }
  15.                 }
  16.         // теперь S[k]=1 тогда и только тогда, когда 2k+1 - простое
  17.         return S;
  18.         }
  19.  
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top