Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Лабораторная №1
- * Проверить число на простоту.
- */
- #include <iostream>
- #include <cmath>
- #include <list>
- using namespace std;
- void simpleNumb(int n)
- {
- bool flag = true;
- for (int i = 2; i <= n; i++) { // N
- if (n % i == 0 && i != n) { // N
- flag = false; //
- break; //
- }
- }
- // Result: O(N)
- flag ? cout << "Simple!\n" : cout << "Not simple!\n";
- }
- void simpleNumb2(int n)
- {
- bool flag = true;
- for (int i = 2; i <= sqrt((float)n); i++) { // sqrt(N)
- if (n % i == 0) { // sqrt(N)
- flag = false; //
- break; //
- }
- }
- // Result: O(sqrt(N))
- flag ? cout << "Simple!\n" : cout << "Not simple!\n";
- }
- void simpleNumbFinal(int n)
- {
- list<int> div;
- div.push_back(2);
- for (int i = 3; i < n + 1; i += 2)
- {
- for (list<int>::iterator j = div.begin(); j != div.end(); j++)
- {
- if (*j > float(sqrt(i)))
- {
- div.push_back(i);
- break;
- }
- else if (i % *j == 0)
- break;
- }
- }
- for (list<int>::iterator i = div.begin(); i != div.end(); i++)
- cout << *i << ' ';
- }
- int main()
- {
- simpleNumb(56783);
- simpleNumb2(56783);
- simpleNumbFinal(56791);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement