In ra các số hoàn hảo bé hơn N

#1

Chuyện là em có code 1 bài tìm số hoàn hảo bé hơn N , nhập các số nhỏ thì thì nó vẫn in ra các số hoàn hảo bình thường, nhưng nhập số to thì chỉ output ra tới 4 số và chạy không nổi nữa .
Em mới học lập trình nên code còn tù , có ai cho em cách giải quyết không ạ.

#include<iostream>

using namespace std;

int main()
{
    long long  n,sum;
    cout << "Enter your number: "; cin >> n;
    for ( int number = 1;number  <= n;number++)
    {
        sum =0;
        for (int i = 1 ; i <= number;i++)
            if (number%i==0)
                sum+=i;
        if (sum/2.0 == number)
            cout << number << endl;
    }
    return 0;
}
#2

5 số hoàn hảo đầu tiên là 6, 28, 496, 8128, 33550336
hiểu lý do vì sao nó chậm rồi ha :3 đơn giản vì nó cực kì hiếm và chẳng có bao nhiêu cả

1 Like
#3

vậy có cách nào để xuất được số hoàn hảo trên 4 mà máy có thể chạy nổi không

#5

Vì nó ít nên chỉ cần tạo sẵn một mảng ra rồi dò theo N :>

3 Likes
#6

input kiểu long, for thì kiểu int nên nó giới hạn tới 32… kiểu in thôi. sửa code lại thì nó sẽ chạy nổi thôi. chỉ là sẽ chậm. cách hay là như bạn ở trên viết lên mạng search ra rồi tạo mảng so sánh kaka. bao nhanh.

#7

Bài này bạn có thể cho chạy biến đếm i rồi check nếu 2^i-1 là số nguyên tố thì in ra số hoàn hảo là 2^(i-1)*(2^i-1)

2 Likes
#8

Vì đơn giản là cắm đầu chạy từ 1 đến N thì sao mà không lâu :smiley:

Thực ra bài này không tiêu biểu lắm, nếu hỏi tổng các ước số thì sẽ thuyết phục hơn là hỏi kiểu này (vì lưu mảng cho cùng là vô nghĩa)

1 Like
#9 
bool isPerfectNumber(int n)
{
    int sum = 0;
    for (int i = 1; i <= n/2; i++)
    {
        if (n % i == 0) sum += i;
    }
    return sum == n;
}

Mình đóng góp một thuật toán tối ưu hơn 1 chút nhé

#10

Thế này vẫn chưa phải là tối ưu, độ phức tạp của thuật của bạn và của bạn thớt đều là O(n) cả.

1 Like
#11

Chưa tối ưu đâu :slight_smile: cận có thể xuống tới sqrt(N) và dấn thêm nữa thì không quá sqrt(N) luôn.

p/s: đã “tối ưu” thì không có “hơn”, “tối” là nhất rồi. Tất nhiên có thể chỉnh thêm nữa.

3 Likes
#12

Oki b ^^ m xem lại đã ^^ cảm ơn b nhé ^^

#13

Oki b ^^ :)) edit nhiều quá mình không kịp trả lời :)) đáng lẽ cái đó phải là tốt hơn thôi chứ b nhỉ :))
Thì đây là cách m mới suy nghĩ khi chủ topic đặt vấn đề :)) nên mình sẽ suy nghĩ thêm ^^ cảm ơn b nhé

#14

Không biết là còn bác nào quan tâm không, nhưng mà mình có cái code chạy O(nlogn).

#include <bits/stdc++.h>
using namespace std;
long long n, tmp, tmp2, sang[100009], nt[100009], S[100009], vt=0, kq[10];
int main(){
    cin>>n;
    fill(sang+2, sang+n+1, 1);
    for(long long i=2; i<=n; i++){
        if(sang[i]){
            for(long long j=i*i; j<=n; j+=i) sang[j]=0;
            vt++;
            nt[vt]=i;
        }
    }
    for(long long i=2; i<=n; i++){
        if(sang[i]){
            S[i]=i+1;
            continue;
        }
        for(long long j=1; nt[j]<=sqrt(i); j++){
            if(i%nt[j]==0){
                tmp=i; tmp2=1;
                while(tmp%nt[j]==0){
                    tmp/=nt[j];
                    tmp2*=nt[j];
                }
                if(tmp==1) S[i]=(i*nt[j]-1)/(nt[j]-1);
                else S[i]=S[tmp]*S[tmp2];
                break;
            }
        }
    }
    S[0]=0; vt=0;
    for(long long i=6; i<=n; i++) 
    if(S[i]==2*i) cout<<i<<endl;
    return 0;
}
#15

Có thể code trong O(1) mà

gopher

Code của bạn là O(n \pi(\sqrt{n})), không phải O(n log n).

2 Likes
#16

hoặc bạn có thể chạy từ 2 đến sqrt(n) :)))

1 Like
#17

Có công thức luôn nè bro
https://vi.m.wikipedia.org/wiki/Số_hoàn_thiện#:~:text=Số%20hoàn%20thiện%20(hay%20còn,trừ%20nó)%20bằng%20chính%20nó.

2 Likes
#19

giải thích cho e chỗ sum chia 2 đc ko ạ

#20

Định nghĩa là ước số không tính n mà cộng lại bằng n. Để ý code #1 + thêm n nên phải so sánh sum với 2*n (viết như trên là sai, vì sao :smiley:) . Thực ra code đó ko hay, bạn đọc thêm mấy reply ấy.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?