Алгоритм сам завершается(хотя должен продолжаться)
Условие: Алгоритм принадлежит числовому отрезку [A;B] (1<A<B<1000000)
выводит числа,имеющие среди делителей ровно три различных натуральных нечетных делителя,
не считая 1 и само число(если оно нечетное).
Для каждого найденного числа выводит в 1 строке через пробел : само число и 3 нечетных делителя.
Пример: 30 3 5 15 , 42 3 7 21 , 54 3 9 27 , 60 3 5 15 , 66 3 11 33
#include <iostream>
using namespace std;
int main()
{
int A,B,g,j,i,c,chislo1,chislo2,chislo3,counter1;
A=30;
B=68;
counter1=0;
chislo1=0;
chislo2=0;
chislo3=0;
if (1<A && B<1000000)
{
for (A;A!=B;A++)
{
for (i=2;i!=A+1;i++)
{
if (A%i==0 && i&2!=0)
{
counter1+=1;
}
}
if (counter1==3)
{
for (i=2;i!=A+1;i++)
{
if (A%i==0 && i%2!=0)
{
chislo1=i;
break;
}
}
for (i=chislo1+1;i!=A+1;i++)
{
if (A%i==0 && i%2!=0)
{
chislo2=i;
break;
}
}
for (i=chislo2+1;i!=A+1;i++)
{
if (A%i==0 && i%2!=0)
{
chislo3=i;
cout<<A<<" "<<chislo1<<" "<<chislo2<<" "<<chislo3<<endl;
counter1=0;
counter1=0;
chislo1=0;
chislo2=0;
chislo3=0;
break;
}
}
}
}
}
else
{
cout<<"Неверный диапазон";
}
return 0;
}
Ответы (2 шт):
Ровно три нечетных делителя могут получиться только в одном случае: если это число четно, имеет ровно 2 различных простых нечетных делителя, причем каждое входит в число только один раз, либо это число имеет вид 2np3, где n > 0.
Так что нужно просто прибегнуть к факторизации и посмотреть, из чего там состоит запрашиваемое число. Поскольку числа до миллиона, проверять надо до 1000, а таблица простых тут невелика — для эффективности можно ее использовать...
#include <vector>
#include <iostream>
using namespace std;
int primes[] = {
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673,
677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761,
769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997 };
bool check(int M)
{
int N = M;
vector<pair<int,int>> f;
if (N%2 == 0)
{
while(N%2 == 0) N/= 2;
}
else return false;
for(int i = 0; i < size(primes) && primes[i]*primes[i] <= N; ++i)
{
pair<int,int> p{0,0};
for(p.first = primes[i]; N%primes[i] == 0; N /= primes[i])
p.second++;
if (p.second) f.push_back(p);
}
if (N > 1) f.push_back(make_pair(N,1));
if (f.size() == 1) // Только если четно, а степень 3
if (f[0].second == 3)
{
int x = f[0].first;
cout << M << " " << x << " " << x*x << " " << x*x*x << endl;
return true;
}
else return false;
if (f.size() == 2 && f[0].second == 1 && f[1].second == 1 ) // Только если оба степени 1
{
cout << M << " " << f[0].first << " "
<< f[1].first << " " << f[0].first*f[1].first << endl;
return true;
}
return false;
}
int main(int argc, char * argv[])
{
int A,B;
cin >> A >> B;
for(int n = A; n <= B; ++n) check(n);
}
Кстати, у меня весь диапазон - 176385 таких чисел - просчитало менее чем за секунду.
Ваша программа не печатает все числа потому что переменная counter1 не сбрасывается в ноль в начале проверки следующего числа. Если она один раз станет больше трёх, ваша программа перестанет печатать числа. Добавление counter1=0; в начале большого цикла улучшает ситуацию.
Теперь ваша программа печатает лишние числа. Например 33 3 11 33. В условии сказано "не считая 1 и само число". В этом примере само число включено в тройку. Чтобы исправить ошибку нужно снизить верхние пределы в четырёх циклах.
Если теперь заменить пределы на максимальные и запустить программу, то за полчаса вы получите все описанные в условии числа.
В условии A%i==0 && i&2!=0 опечатка: вместо амперсанда должен быть процент. Пара минут с таблицей приоритетов операторов показывают что это именно опечатка: второе подусловие по-прежнему отбирает нечётные значения i.
Если довести ваши идеи до реализации получится что-то такое:
#include <iostream>
int main() {
int a, b;
if (!(std::cin >> a >> b)) {
return 1;
}
for (int n = a; n < b + 1; ++n) {
const int K = 3;
int divisors[K];
int j = 0;
for (int i = 3; i < n; i += 2) {
if (n % i == 0) {
if (j >= K) {
j = 0;
break;
}
divisors[j] = i;
++j;
}
}
if (j == K) {
std::cout << n;
for (int j = 0; j < K; ++j) {
std::cout << ' ' << divisors[j];
}
std::cout << '\n';
}
}
}
$ g++ -g -O0 -std=c++17 -pedantic -Wextra -Werror temp.cpp $ time echo 1 999999 | ./a.out > out real 7m12.618s user 7m11.124s sys 0m0.156s $ head out 30 3 5 15 42 3 7 21 54 3 9 27 60 3 5 15 66 3 11 33 70 5 7 35 78 3 13 39 81 3 9 27 84 3 7 21 102 3 17 51 $ tail out 999934 13 38459 499967 999942 3 166657 499971 999962 37 13513 499981 999974 17 29411 499987 999976 239 523 124997 999980 5 49999 249995 999982 79 6329 499991 999986 13 38461 499993 999988 11 22727 249997 999994 23 21739 499997 $ wc -l out 176395 out
Другой подход состоит в отказе от поиска и перехода к порождению нужных чисел.
Любое натуральное число может быть представлено в виде произведения степеней простых: n = 2e0·p1e1·p2e2·p3e3·.... Здесь pi - различные нечётные простые, ei - натуральные. Сила этого произведения в том что комбинируя его множители можно построить любой делитель исходного числа.
Пусть в разложении найдётся хотя бы три нечётных простых - p1, p2, p3. Тогда они сами - нечётные делители n и p1p2 - тоже нечётный делитель n. Слишком много.
Если в разложении ровно два простых нечётных, но степень у одного из них больше единицы, то p1, p2, p1p2, p12 - нечётные делители. Опять слишком много.
Если разложение есть n = 2e·p1p2, то у нас равно три нечётных делителя: p1, p2 и p1p2. e должно быть больше нуля. Иначе старший нечётный делитель совпадёт с самим числом.
Остались разложения в котором ровно один нечётный простой множитель. Нам подходит n = 2e·p3 с делителями p, p2 и p3. e больше нуля.
Последний вариант без чётных можителей: n = p4. Делители: p, p2 и p3. Других разложений нет.
Для построения разложений нужно сделать список простых чисел. Решето Эратосфена справится мгновенно в диапазоне до миллиона.
Вот программа-генератор:
#include <iostream>
#include <vector>
std::vector<int> sift(int n) {
std::vector<bool> sieve(n, true);
for (int i = 2; i < n; ++i) {
if (sieve[i]) {
for (int j = 2 * i; j < n; j += i) {
sieve[j] = false;
}
}
}
std::vector<int> primes;
for (int i = 2; i < n; ++i) {
if (sieve[i]) {
primes.push_back(i);
}
}
return primes;
}
int main() {
int a, b;
if (!(std::cin >> a >> b)) {
return 1;
}
const std::vector<int> primes = sift(b + 1);
for (int p : primes) {
if (p == 2) {
continue;
}
int q = p * p * p * p;
if (q > b) {
break;
}
if (q >= a) {
std::cout << q << ' ' << p << ' ' << p * p << ' ' << p * p * p << '\n';
}
}
for (int p : primes) {
if (p == 2) {
continue;
}
int q0 = 2 * p * p * p;
if (q0 > b) {
break;
}
for (int q = q0; q <= b; q *= 2) {
if (q >= a) {
std::cout << q << ' ' << p << ' ' << p * p << ' ' << p * p * p << '\n';
}
}
}
const int n = primes.size();
for (int i = 1; i < n - 1; ++i) {
int p1 = primes[i];
if (2 * p1 * p1 > b) {
break;
}
for (int j = i + 1; j < n; ++j) {
int p2 = primes[j];
for (int q = 2 * p1 * p2; q <= b; q *= 2) {
if (q >= a) {
std::cout << q << ' ' << p1 << ' ' << p2 << ' ' << p1 * p2 << '\n';
}
}
}
}
}
На моём компьютере она выдаёт 176395 чисел за 0.2 секунды. Обратите внимание что порядок чисел нарушен. Если это проблема, их надо накапливать в массиве и сортировать перед печатью.