Занятие 1

Простые числа

Определение простоты числа (`n`>1, 1 не является ни простым, ни составным):

bool isprime(int n)
{
  int i,m;
  m=sqrt(n);
  for(i=2; i<=m; ++i)
    if(n%i==0) return false;
  return true;
}

Следующий вариант не работает на больших простых числах (например, 2147483647) из-за ошибки переполнения в операции умножения i*i:

bool isprime(int n)
{
  int i;
  for(i=2; i*i<=n; ++i)
    if(n%i==0) return false;
  return true;
}

Функцию можно немного ускорить, проверяя только нечетные числа:

bool isprime(int n)
{
  int i,m;
  m=sqrt(n);
  if(2<=m && n%2==0) return false;
  for(i=3; i<=m; i+=2)
    if(n%i==0) return false;
  return true;
}

Для нахождения всех простых чисел до `n` самым эффективным алгоритмом является решето Эратосфена:

  const int N=1000000;
  bool p[N+1]={0};
  int m=sqrt(N);
  for(i=2; i<=N; ++i) p[i]=1;
  for(i=2; i<=M; ++i)
    if(p[i]) // находим невычеркнутое число
    { for(j=i*i; j<=N; j+=i)
        p[j]=0; // вычеркиваем все числа, кратные i
    }

Получение набора простых чисел от 1 до `n` с помощью решета:

void resheto(int n, vector<int> &r)
{ 
  int m=sqrt(n), i, j, k;
  vector<char> p(n+1,1); // отмечаем все числа флажком 1
  // решето
  for(i=2; i<=m; ++i)
    if(p[i]) // находим невычеркнутое число
    { for(j=i*i; j<=n; j+=i)
        p[j]=0; // вычеркиваем все числа, кратные i
    }
  // переписываем оставшиеся числа в массив r
  r.resize((n>200?n/(log(n)-2):1.6*n/log(n))+1);
  k=0;
  for(i=2; i<=n; ++i)
    if(p[i])
      r[k++]=i;
  r.resize(k);
}