Нахождения НОК(от 1 до n)

Question

Суть задачи нахождения НОК(от 1 до n чисел) 1<=n<=1000

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n, p, a, d, t, j;
    vector<double long> B;
    vector<double long> C;
    cin >> n;
    if (n == 1)
    {
        cout << "1";
        return 0;
    }
    long long* A = new long long[n];
    a = 2;
    for (int i = 0; i < n - 1; i++)
    {
        A[i] = i + 2;
        if (a < A[i]) a = A[i];
    }
    d = 2;
    j = 0;
    while (d <= a)
    {
        if (a % d == 0)
        {
            B.push_back(d);
            a = a / d;
            j++;
        }
        else
            d = d + 1;
    }
for (int k = 0; k < j; k++) 
    C.push_back(B[k]);

p = C.size();

for (int k = 0; k < n - 1; k++)
{
    d = 2;
    while (d <= A[k])
    {
        while (A[k] % d == 0 && d <= A[k])
        {
            for (int i = 0; i < p; i++)
            {
                if (B[i] == d)
                {
                    B.erase(B.begin() + i);
                    t = 0;
                    p = p - 1;
                    break;
                }
                if (B[i] != d) 
                    t = 1;
            }
            if (t != 0) 
                C.push_back(d);
            A[k] = A[k] / d;
        }
        d = d + 1;
    }
    p = C.size();
    B.clear();
    for (int i = 0; i < p; i++) 
        B.push_back(C[i]);
}
p = 1;
n = C.size();
for (int k = 0; k < n; k++)
    p = p * C[k];

cout << p;
}

Прошла 17 тестов. Не находит значение в 1000.

Answer 1

Вот такое решение попробуйте:

#include <vector>
#include <iostream>
#include <cstdio>


using namespace std;

vector<unsigned int>& operator *=(vector<unsigned int>& v,
                                  unsigned int d) {
    int carry = 0;

    for (int i = 0; i < v.size(); ++i) {
        v[i] *= d;
        v[i] += carry;
        carry = v[i] / 1000000;
        v[i] %= 1000000;
        }

    if (carry) v.push_back(carry);

    return v;
    }

bool prime(unsigned int m) {
    for (unsigned int i = 2; i * i <= m; ++i)
        if (m % i == 0) return false;

    return true;
    }

int main() {
    vector<unsigned int> v = {1};
    unsigned int n;
    cin >> n;

    for (unsigned int k = 2; k <= n; ++k) {
        if (prime(k)) {
            int m = 0;

            for (int p = 1;;) {
                p *= k;

                if (p <= n) {
                    v *= k;
                    ++m;
                    }
                else break;
                }
            }
        }

    for (int i = v.size() - 1; i >= 0; --i) {
        if (i == v.size() - 1) printf("%d", v[i]);
        else printf("%06d", v[i]);
        }
    }

БЛОГ НА HUSL

Нахождения НОК(от 1 до n)

Ответы (1 шт):