Bodigrim

Sieve of Eratosthenes by odd numbers

Nov 20th, 2011
6,265
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