Question

Товарищи,говорю сразу,задачка не школьного уровня и нужна сегодня к вечеру или завтра к утру,тому кто решит много баллов! Вася занимается в математическом кружке и интересуется различными свойствами чисел.Недавно он изучил понятие простого числа. Напомним, что натуральное число n называется простым, если n > 1 и у него есть ровно два делителя: 1 и n. Особо интересными Вася считает числа, которые представимы в виде произведения двух различных простых чисел. Вася очень хочет найти количество таких чисел среди чисел от 1 до n,однако считать его вручную не хочет. Поэтому он попросил вас написать для него программу,которая будет вычислять это количество. Задано число п. Необходимо найти количество чисел х от 1 до n, которые представимы в виде произведения двух различных простых чисел.P/S. Составить блок схему к задаче ;))

Answer 1

Pascal

 var   
n,i,k : integer;    
function Prost (a : integer) : boolean;  //Возвращает true если число простое
var   
i,b : integer;   
r : boolean; 
begin   
r := true;   
i := 2;   
b := a div 2;   
While (i <= b) and (r) do   
begin     
if a mod i = 0 then     
r := false;   
i := i +1;   
end;   
Result := r; 
end;  

function chet (l : integer) : integer; //Определяет кол-во     
var   i,s : integer;                        //возможных произведений 
                                                 // в числовой последовательносьти
                                                 //заданной длины
begin   
  s := 0;   
for i := 0 to k do     
s := s +(k - i);    
result := s;     
end;
begin 
readln (n); 
k := 0;     
for i := 2 to n do   
if prost(i) then begin     
k := k +1;      
//write (i,' '); // Вывод простых чисел(если надо, то раскоменьтить)     
end;   
writeln ();
writeln ('Кол-во простых чисел на диапазоне = ',k); 
writeln ('Кол-во произведений ',k,' различных чисел : ',chet(k));    
end.  

Вроде работает, хотя вероятно есть более эффективный алгоритм.
Единицу не учитывал как простое.
Блок схему рисовать не буду - геморойной, да и не силен я в этом

Просто попытаюсь объяснить алгоритм

1) Мы находим все простые числа на диапазоне от 1 до n
(выполняется функцией (prost), и перебором.
2) Исходя из кол-ва найденных простых чисел мы можем найти кол-во их произведений. Т.к все числа различны и идут в порядке увеличения.
Это делается с помощью функции (chet)

Answer 2

Для решения этой задачи можно использовать следующий алгоритм:

1. Инициализировать переменную count = 0, которая будет считать количество чисел, удовлетворяющих условию.

2. Создать функцию is_prime(number), которая будет проверять, является ли число number простым. Внутри функции можно использовать обычную проверку делителей числа.

3. Проитерироваться по числам от 1 до n включительно:

   3.1. Для каждого числа i проверить, является ли оно простым, используя функцию is_prime(i).

   3.2. Если i - простое число, найти все простые числа j, такие что 1 < j < i.

   3.3. Для каждого найденного простого числа j проверить, является ли число i/j простым, используя функцию is_prime(i/j).

   3.4. Если i/j - простое число и i/j не равно j, увеличить count на 1.

4. Вернуть значение count.

Блок-схема к данной задаче:

cssCopy code
┌───────────────────────┐
│      Начало программы       │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│    Ввод значения n       │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│     Инициализация count  │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│    Функция is_prime      │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│        Итерация           │
│          по числам i         │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│  Проверка простоты i   │
│       (is_prime(i))       │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│  Итерация по числам j  │
│    (1 < j < i)             │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│   Проверка простоты     │
│  числа i/j (is_prime(i/j)) │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│    Проверка условия      │
│        и увеличение       │
│         count               │
└───────────────────────┘
                │
                ▼
┌───────────────────────┐
│     Конец программы      │
└───────────────────────┘

Надеюсь, это поможет вам составить программу