题目一:列出完数
Description:自然数中,完数寥若晨星,请在从1到某个整数范围中打印出所有的完数来。 所谓“完数”是指一个数恰好等于它的所有不同因子之和。例如,6是完数,因为6=1+2+3。而24不是完数,因为24≠1+2+3+4+6+8+12=36。
Input:输入数据中含有一些整数n(1<n<10000)。
Output:对于每个整数n,输出所有不大于n的完数。每个整数n的输出由n引导,跟上冒号,然后是由空格开道的一个个完数,每个n的完数列表应占独立的一行。
代码如下:
#include<iostream> #include<vector> using namespace std; class PerfectNumber { private: int a; vector<int>perfect_nums; public: PerfectNumber(int a) :a(a) {} void calculate(){ for (int i = 1; i <= a; i++) { int sum = 0; for (int j = 1; j < i; j++) { if (i % j == 0) { sum += j; } } if (i == sum) { perfect_nums.push_back(i); } } } void print()const { for (const auto& num : perfect_nums) { cout << num << " "; } cout << endl; } }; int main() { int n; while (cin >> n) { while (n != 0) { PerfectNumber PN(n); PN.calculate(); PN.print(); cin >> n; } } return 0; }
运行结果:
题目二:Semi-Prime
Prime Number Definition An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.Semi-Prime Number Definition An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.Your task is just to determinate whether a given number is a semi-prime number.
Input:There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000]
Output:One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No"
运行代码:
#include<iostream> #include<vector> #include<cmath> using namespace std; class SemiPrime { private: int n; public: SemiPrime(int n):n(n){} bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } bool isSemiPrime(int n) { if (isPrime(n)) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0 && isPrime(i) && isPrime(n / i)) { return true; } } return false; } }; int main() { int n; while (cin >> n) { SemiPrime SP(n); //SP.isPrime(n); if (SP.isSemiPrime(n)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }
运行结果:
题目三:12!配对
Description:找出输入数据中所有两两相乘的积为12!的个数。
Input:输入数据中含有一些整数n(1<2^32)
Output:输出所有两两相乘的积为12!的个数.
#include <iostream> #include <unordered_map> #include <vector> #include<algorithm> using namespace std; const long long F12 = 479001600; class PairCounter { private: unordered_map<long long, int> m; public: void add(long long number) { m[number]++; } int countPairs() { int count = 0; long long target = F12; for (auto& pair : m) { long long number = pair.first; int a = pair.second; if (m.count(target / number) && number != target / number) { count += a * m[target / number]; } else if (number * number == target) { if (a >= 2) { count += a * (a - 1) / 2; } } } return count / 2; } }; int main() { PairCounter counter; long long n; while (cin >> n) { counter.add(n); } cout << counter.countPairs() << endl; return 0; }
运行结果:
#include<iostream> #include<set> const long long int f12 = 479001600; using namespace std; int main(){ int num = 0; multiset<int> s; for (int n; cin >> n;) { if (f12 % n == 0) { set<int>::iterator it = s.find(f12 / n); if (it != s.end()){ num++; s.erase(it); } else{ s.insert(n); } } } cout << num << endl; return 0; }
注意点:这个与题干要求输入方式不同,所以需要再研究研究
题目四:整数的因子数
Description:找出整数的所有因子数。 一个整数n的因子数为包含它自身的所有因子的个数。例如:12的因子数为6(1,2,3,4,6,12)。
Input:输入数据中含有一些整数n(1sn<2^32)。
Output:对于每个n,列出其所有因子数,每个n加上冒号单独列一行。
代码如下:
#include<iostream> #include<algorithm> #include<vector> using namespace std; class Factor { public: int count(int n) { int count = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { count += 2; } } if (sqrt(n) * sqrt(n) == n) { count--; } return count; } }; int main() { Factor f; int n; while (cin >> n) { cout << n << ":" << f.count(n) << endl; } return 0; }
运行代码