Лабораторна робота: «Виведення простих чисел»

Тема. Рекурентні цикли. Оператори while та do-while.

«Виведення простих чисел»

ТЕОРЕТИЧНІ ВІДОМОСТІ

ЗАВДАННЯ ДЛЯ ВИКОНАННЯ

Дано: два натуральних числа a та b.
Знайти: Для кожного з чисел a, a+1, a+2,..., b  з’ясувати, чи є воно простим. Якщо число просте, то вивести його на екран.

ЗМІННІ:

Вхідні:
a – ліва границя інтервалу (цілого типу int)
b – права границя інтервалу (цілого типу int)

Вихідні:
p – ознака наявності дільників (логічного типу, p=false немає дільників, p=true є дільники )

Проміжні:
n – натуральне число з інтервалу [a, b] та параметр зовнішнього циклу (цілого типу int, бо число натуральне)
i – дільники числа n та параметр внутрішнього циклу (цілого типу int)

АЛГОРИТМ

1. Спочатку вводимо натуральні числа a та b, що є границями інтервалу.
2. Для кожного числа n із цього інтервалу ми повинні повністю виконати попередній алгоритм, починаючи з пункту 2. Тому у нас будуть вкладені цикли:

• зовнішній цикл:

- перебирає числа n з інтервалу [a, b]
- присвоює початкове значення ознаці p=false. Тобто вважаємо, що дільників у числа n немає. Це обов’язково потрібно зробити у зовнішньому циклі, але перед внутрішнім.

• У внутрішньому циклі будемо шукати дільники числа n. 
• Коли внутрішній цикл закінчиться, то перевіримо значення ознаки:

- якщо p=false, то дільників немає, число n - просте і тому виводиться на екран, а потім виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.
- якщо p=true, то є дільники, число не просте, число не виводиться, виконується перехід на наступний виток зовнішнього циклу для обробки наступного числа.

ПРИКЛАД ПРОГРАМИ

package prostiNumbers;
import java.util.Scanner; //імпорт класу
public class Primes {
//Для кожного з чисел a, a+1, a+2,..., b  з’ясувати, чи є воно простим. 
//Якщо число просте, то вивести його на екран.
 public static void main(String[] args) {
  Scanner a = new Scanner(System.in); //створення об'єкту класу Scanner - a
  Scanner b = new Scanner(System.in); //створення об'єкту класу Scanner - b
        int x=0, y=0, n=0, i=0;
        boolean p;
        System.out.println("Введіть a: ");
        System.out.println("Введіть b: ");
        if(a.hasNextInt() && b.hasNextInt()) { 
//повертає істина, якщо введено ціле число, зчитує ціле число і записує в змінну
          x = a.nextInt();   
          y = b.nextInt(); 
          System.out.print("В ітервалі "+"["+x+","+y+"] "+"прості числа: ");
          for(i=x; i<=y; i++){
//розглядаємо тільки непарні числа, бо серед парних простим є тільки 2
           if(i%2==1){
            p=true;
            n=3;
            while(n<i/2 && p){
             if(i%n==0){
              p=false; 
             }
             else n=n+2;
            }
            if(p=true)
             System.out.print(i+", ");
           } 
           
          }
         }else{
          System.out.println("Ви ввели не ціле число a,b");
         }

 }

}

РЕЗУЛЬТАТ

Введіть a: 
Введіть b: 
10
50
В ітервалі [10,50] прості числа: 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 

Пояснення:

Вводимо числа 10 та 50.
Для кожного з чисел 10, 11, 12, ... шукаємо дільники в інтервалі [2,n div 2].
У числа 10 в інтервалі [2,5] є дільники 2 та 5, тобто число не просте.
У числа 11 в інтервалі [2,5] немає дільників, тобто число просте і тому виводиться на екран.
У числа 12 в інтервалі [2,6] є дільники 2, 3, 4 та 6, тобто число не просте.
У числа 13 в інтервалі [2,6] немає дільників, тобто число просте і тому виводиться на екран.
У числа 14 в інтервалі [2,7] є дільники 2 та 7, тобто число не просте.