Kiểm tra 1 số có phải số hoàn hảo không C++

Tuan_Cris · November 25, 2019, 3:30am

e muốn nhờ các a xem giúp code của e về bài này,e chạy trên dev c++ thì đúng nhưng khi lên spoj thì luôn bị quá thời gian,e tuy sửa hoài mà chưa được,đây là lần đầu e đăng bài nên có gì chưa đúng các a góp ý cho e

#include<iostream>
using namespace std;
 
int tinhtong(int n) 
{  
    int sum = 1; 
    for ( int i=2; i*i < n; i++) 
    { 
        if (n%i==0) 
        { 
            if(i*i != n)
                sum = sum + i + n/i; 
            else
                sum = sum + i; 
        } 
    }   
    return sum;
} 
int main()
{
	int T,n;
	cin >> T;
	while(T--)
	{
		cin >> n;
	    if(tinhtong(n) == n && n != 1 )
	         cout << "1" << endl;
	    else cout << "0" << endl;
	}
	return 0;
}

DoTran1 · November 25, 2019, 3:23am

if này luôn luôn đúng mà @@
bạn thử đưa dòng if else này ra khỏi vòng for (khai báo lại biến i bên ngoài for)
kết thúc vòng for mới kiểm tra

if (i*i == a){ 
    sum += i;
}

DoTran1 · November 25, 2019, 3:34am

mà kể ra code của bạn sao chạy đúng được nhỉ?
Trường hợp số hoàn hảo là 1 số chính phương, code bạn sai chắc luôn!

Tuan_Cris · November 25, 2019, 3:37am

a có thể sửa theo ý anh cho e xem với đc ko ạ

DoTran1 · November 25, 2019, 3:47am

iem nó mới mà, còn trinh nguyên
có ý tưởng gì chỉ em nó đi

DoTran1 · November 25, 2019, 3:42am

int tinhtong(int n) 
{  
    int sum = 1; 
	int i = 2;
    for (i=2; i*i < n; i++) { 
        if (n%i==0) 
        { 
            sum = sum + i + n/i; 
        } 
    }   
	if (i*i == a){ 
		sum += i;
	}
    return sum;
}

Chưa test!

Tuan_Cris · November 25, 2019, 3:52am

cái chỗ a kia là n chứ a nỉ,e sửa lại test trên dev c++ thì cũng đúng nhưng cứ lên spoj thì lần này ko phải chạy quá time mà là sai ạ

Tuan_Cris · November 25, 2019, 3:55am

theo e biết thì số hoàn hảo có dạng (2^p-1)*2^(p-1),hình như ko có số chính phương là số hoàn hảo

DoTran1 · November 25, 2019, 4:02am

Làm sao sai được nhỉ?
bạn xóa luôn đoạn này đi rồi chạy lại xem =,=

if (i*i == n){ 
		sum += i;
}

hoặc thử chuyển sum += i ; thành sum = sum + i; xem được không?
Cách nữa bạn thử tạo thêm 1 biến int can2 = sqrt(n) rồi cho for i chạy từ 2 đến can2 xem có bớt được ít tg nào không?
chứ tôi k biết sai ở đâu luôn

DoTran1 · November 25, 2019, 5:02am

Đây có phải bài toán của bạn không?

Cái comment của bạn Vương Trung Hiếu Nghĩa

2019-03-21 10:26:24
#include
#include

using namespace std;

int main() {
int n,MAX;
cin >> n;
MAX = n;
int SUM =0;
while(n>0){
n=n%2;
SUM +=n;
if(SUM==MAX){
cout << “YES” ;
}
if(n<1) cout << “NO” ;

}

return 0;

}

là đáp án à? Lạ vậy? Tôi không nghĩ code đó đúng @@
bạn sửa chạy được chưa?

DoTran1 · November 25, 2019, 6:44am

Code tôi viết bằng java, chạy ổn mà

 public static void main(String[] agrs) {
    	int n = 10000;
    	System.out.println("Những số hoàn hảo từ 2 đến " + n + " là: ");
    	for (int i = 2; i< n; i++) {
    		if (isPerfect(i)) {
    			System.out.print(i + " ");
    		}
    	}
    }
    private static boolean isPerfect (int n) {
    	if (n < 2) return false;
    	int sum = 1, i = 2;
    	for (i = 2; i*i < n; i++) {
    		if (n % i == 0) {
    			sum += i + n/i;
    		}
    	}
    	if (i*i == n) {
    		sum =+ i;
    	}
    	if (sum == n) return true;
    	else return false;
    }

Đây là kết quả

Những số hoàn hảo từ 2 đến 10000 là: 
6 28 496 8128

Tuan_Cris · November 25, 2019, 8:27am

e ko nói code a sai gì đâu có cái kỳ thi này e thi trên spoj nên làm sao code phải xanh mới có điểm anh à

rogp10 · November 25, 2019, 8:36am

Thay vì i*i thì #include <cmath> luôn
Chuyển qua phân tích thừa số nguyên tố.
Nhảy i theo điệu 2-4.

DoTran1 · November 25, 2019, 10:58am

nè bạn. SPOJ báo sai nè

Sherly1001 · November 25, 2019, 1:17pm

Đề cho N giới hạn trên là 10¹⁸ thì chỉ có 7 số là số hoàn hảo thôi.

7 số đầu của dãy là [6, 28, 496, 8128, 33550336, 8589869056, 137438691328] (tham khảo ở đây).

Vậy chỉ cần check n xem có bằng những số này không là được rồi, viết hàm check chi cho mệt. :v :v :v

#include <iostream>

const long long perfectNumbers[7] = {6, 28, 496, 8128, 33550336, 8589869056, 137438691328};

bool isPerfectNumber(long long n) {
    for (int i = 0; i < 7; i++) if (n == perfectNumbers[i]) return true;
    return false;
}

int main() {
    int t = 0;
    long long n = 0;
    
    std::cin >> t;
    
    for (; t; --t) {
        std::cin >> n;
        std::cout << isPerfectNumber(n) << '\n';
    }
    return 0;
}

tntxtnt · November 25, 2019, 1:36pm

#include <iostream>
#include <algorithm>

int main() {
    long long n, p[] = {6, 28, 496, 8128, 33550336, 8589869056, 137438691328};
    for (std::cin >> n; std::cin >> n;)
        std::cout << (std::find(p, p + 7, n) != p + 7) << "\n";
}

3 dòng thôi

DoTran1 · November 25, 2019, 2:33pm

Vậy lại nhanh quá :)))))