Algoholic.in.ua

Решения > Простые числа. Решето Эратосфена

Простые числа. Решето Эратосфена JavaС++

Категория: Решения | Добавлено: 2015-08-29 | Просмотров: 1865

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n.


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


Алгоритм:

  1. Выписываем все числа от 2 до n.
  2. Вычеркиваем из списка все числа от 2i до n с шагом i (при первом прохождении i=2, так как это первое простое число).
  3. Находим следующее не зачеркнутое число в списке.
  4. Повторяем пункты 2-3, пока это возможно.

Код реализации на Java:

        import java.util.Arrays;
        public static void main(String[] args) {
          int n = 1000,amount = 0;
          boolean[] primes = new boolean[n];
          //1
          Arrays.fill(primes,true);
          primes[0] = primes[1] = false;
          for (int i = 2; i < primes.length; i++) {
              //2,3,4
              if(primes[i]) {
                  for (int j = 2; i * j < primes.length; j++) {
                      primes[i * j] = false;
                  }
                  System.out.println(i);
                  amount++;
              }
          }
          System.out.println("Количество простых чисел: "+amount);
        }
        

Код реализации на C++:

          #include <iostream>
          #include <vector>

          using namespace std;

          int main()
          {
              setlocale(LC_CTYPE, "rus");
              int n,amount = 0;
              cin >> n;
              //1
              vector <bool> prime(n + 1, true);
              prime[0] = prime[1] = false;
              //2,3,4
              for(int i = 2; i < = n; ++i)
                  if(prime[i]){
                      for (int j = 2; i * j <= n; j++)
                          prime[i * j] = false;
                  cout << i << endl;
                  amount++;
              }
              cout << "Количество простых чисел: " << amount;
              return 0;
          }
        

Пример 1:
n = 10
Результат:
2
3
5
7
Количество простых чисел: 4


Яндекс.Метрика
Украина онлайн