Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].
Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].
Выходные данные:
Некоторое количество натуральных чисел.
Тесты.
№ | Входные данные | Выходные данные | |
[latex]a[/latex] | [latex]b[/latex] | [latex]p[/latex] | |
1 | 1 | 4 | 2, 3 |
2 | 0 | 1 | Not found |
3 | 5 | 5 | 5 |
4 | 6 | 20 | 7, 11, 13, 17, 19 |
Код программы (C++).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <vector> using namespace std; int main() { cout<<"Primes: "; bool prime; int a,b; cin>>a>>b; vector<int> primes; for(int e=2; e<=b; e++) { prime=true; for(int i=0; i<primes.size(); i++) { if((e%primes[i])==0) prime=false; } if(prime==true) { primes.push_back(e); if(e>=a) cout<<e<<" "; } } if(b<2) cout<<"Not found."; return 0; } |
Код программы (Java).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.*; import java.math.*; class sieveOfEratosthenes { public void find(int a, int b){ boolean[] prime = new boolean[b+1]; Arrays.fill(prime, Boolean.TRUE); prime[0] = false; prime[1] = false; for(int i = 2; i <= b; ++i){ if(prime[i]){ for(int j = i*i; j <= b; j += i){ prime[j] = false; } } } boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число? for(int i = a; i <= b; ++i){ if(prime[i]){ System.out.print(i + " "); primes_found = true; } } if(!primes_found) System.out.print("Not found"); } } class Main { public static void main (String[] args) { Scanner in = new Scanner(System.in); int a, b; a = in.nextInt(); b = in.nextInt(); sieveOfEratosthenes c = new sieveOfEratosthenes(); c.find(a, b); } } |
Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)