Рубрики

Java программа для сита эратосфена

Учитывая число n, выведите все простые числа, меньшие или равные n. Также дано, что n — небольшое число.
Например, если n равно 10, вывод должен быть «2, 3, 5, 7». Если n равно 20, выходное значение должно быть «2, 3, 5, 7, 11, 13, 17, 19».

Джава

// Java-программа для печати всех простых чисел, меньших или равных
// n сито Эратосфена

  

class SieveOfEratosthenes

{

    void sieveOfEratosthenes(int n)

    {

        // Создаем логический массив "prime [0..n]" и инициализируем

        // все записи это как правда. Значение в простом [i] будет

        // наконец, ложь, если я не простое число, иначе истина.

        boolean prime[] = new boolean[n+1];

        for(int i=0;i<n;i++)

            prime[i] = true;

          

        for(int p = 2; p*p <=n; p++)

        {

            // Если простое число [p] не изменилось, то это простое число

            if(prime[p] == true)

            {

                // Обновить все кратные р

                for(int i = p*2; i <= n; i += p)

                    prime[i] = false;

            }

        }

          

        // Распечатать все простые числа

        for(int i = 2; i <= n; i++)

        {

            if(prime[i] == true)

                System.out.print(i + " ");

        }

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int n = 30;

        System.out.print("Following are the prime numbers ");

        System.out.println("smaller than or equal to " + n);

        SieveOfEratosthenes g = new SieveOfEratosthenes();

        g.sieveOfEratosthenes(n);

    }

}

  
// Этот код предоставлен Амитом Хандельвалом.

Выход:

Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29

Пожалуйста, обратитесь к полной статье о сите Эратосфена для более подробной информации!

Рекомендуемые посты:

Java программа для сита эратосфена

0.00 (0%) 0 votes