Пять Чисел Задача C++

231

16 апреля 2019, 12:10

Написал такой код, проходит половину тестов, из тех что не проходят - половина ограничение по времени, половина неверный ответ. Где в коде ошибка и как её исправить? Задача:

Код :

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int nextPrime(int n) {
    n++;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return nextPrime(n);
    return n;
}
bool isExpOf2(long int x) {
    return ((x != 0) && ((x & (~x + 1)) == x));
}
int main() {
    ifstream inp;
    ofstream otp;
    inp.open("input.txt");
    otp.open("output.txt");
    long int k = 0, p = 0, a[5], tempx100;
    double temp;
    for (int i = 0; i < 5; i++) {
        inp >> a[i];
    }
    for (int i = 0; i < 5; i++) {
        p = nextPrime(1);
    k:
        temp = a[i];
        temp /= p;
        tempx100 = temp * 100;
        if (p > a[i]) {
            otp << "NO" << endl;
            continue;
        }
        if (tempx100 % 100 == 0) {
            if (isExpOf2((int)temp)) {
                otp << "YES" << endl;
                continue;
            }
            else {
                p = nextPrime(p);
                goto k;
            }
        }
        else {
            p = nextPrime(p);
            goto k;
        }
    }
    return 1;
}

Answer 1

Что-то у вас наверчено такого, что разобраться, что вы делаете, не получается...

bool isPrime(int n)
{
    for(int i = 3; i*i <= n; i+=2)
        if (n%i==0) return false;
    return true;
}

bool format(int n)
{
    while(n%2==0) n/=2;
    return isPrime(n);
}
int main(int argc, const char * argv[])
{
    ifstream inp("input.txt");
    ofstream otp("output.txt");
    for(int n, i = 0; i < 5; ++i)
    {
        inp >> n;
        otp << (format(n) ? "YES\n" : "NO\n");
    }
}

Answer 2

Понятия не имею почему ваша задача неверна, может изза проверки на простоту до корня. Приведу свою идею.

Мне кажется у вас похожая была :) А идея такова:с помощью решета Эратосфена ищем наименьшее число p такое что A[i] / p = 2 ^ k.

Ну эту проверку можно сделать с помощью функции двоичного логарифма. Ну и вроде все.

Краткая реализация на python:

from math import log2
a = list(map(int,input().split()))
MAX = 100 # Выберете число под лимит задачи :)
prime = MAX*[1]
#если число 1 - не простое,то дописать: prime[1] = 0
arr = []
#Решето Эратосфена
for i in range(2,MAX):
    if prime[i]:        
        j = i*i
        arr.append(i)
        while j < MAX:
            prime[j] = 0
            j+=i
for i in range(0,5):
    q = 0
    for j in range(0,len(arr)):
        if log2(a[i]/arr[j])==int(log2(a[i]/arr[j])):
            q = 1
            break
    if q==0:print("NO")
    else:print("YES")