Kiểm tra có phải số Sphenic hay không

#1

Mình có bài này mn có ý tưởng gì hay ho thì giúp với ạ ^^
Mình xin cảm ơn.
bài toán:
Số nguyên dương N được gọi là số Sphenic nếu N được phân tích duy nhất dưới dạng tích của ba số khác nhau. Ví dụ N=30 là số Sphenic vì 30 = 2×3×5; N = 60 không phải số Sphenic vì 60 = 2×2×3×5. Cho số tự nhiên N, nhiệm vụ của bạn là kiểm tra xem N có phải số Sphenic hay không?

#3

là thuật toán hay là j v ạ ???

#4

e xin lỗi e đọc nhầm :))

#5

e tìm trên mạng ko thấy bài viết về số tri-primes, chỉ kĩ giúp e đc ko ạ :((

#6

Sao không tìm Sphenic có trong đề bài luôn cho xong. :rofl:

5 Likes
#7

ko có a ơi, e đang địh đú theo sàng eratosthenes xem sao :))

#8

chia từ từ cũng ra mà :thinking:

int primeDivisorCount = 0;
for (int s = sqrt(n), i = 2; i <= s; ++i)
    while (n % i == 0) n /= i, primeDivisorCount++;
if (n != 1) primeDivisorCount++;
return primeDivisorCount == 3;

:thinking:

edit 1: i phải chạy tới floor(sqrt(n))
edit 2: phải cộng thêm 1 nếu n != 1 sau khi ra khỏi vòng lặp chia từ từ :V

edit: chạy thử https://rextester.com/NNGQ44636

danh sách đối chiếu: http://oeis.org/A014612 :V

4 Likes
#9

kết quả này chưa đúng này bạn, đề bài yc:

Theo tôi phải lưu các giá trị i thỏa mãn lại, điều kiện so sánh phải bổ sung n != []i
VD: số 63 = 3 * 3 * 7 => Không phải số Sphenic

4 Likes
#10 
# [1..n] is 1 to n
-> n
: i
for i in [2..n**(1/3)] do break if n % i == 0
<- false if i > n**(1/3) || (n/=i) % i == 0
# 2 factors left
for i in [i..sqrt(n)] do break if n % i == 0
<- (n != i * i)
1 Like
#11

cái này lỡ n=2x3x3x5 chỗ return nó cũng return true nhỉ? :V

chả lẽ phải dùng mảng :V

edit: chắc thêm 1 dòng :V

int distinctPrimeDivisorCount = 0;
for (int s = sqrt(n), i = 2; i <= s; ++i) {
    if (n % i == 0) n /= i, distinctPrimeDivisorCount++;
    if (n % i == 0) return false; // trùng
}
// if (n != 1) distinctPrimeDivisorCount++;
// return distinctPrimeDivisorCount == 3;
return distinctPrimeDivisorCount + (n != 1) == 3; //gộp bỏ if nhanh hơn 1 tí :V

chạy thử: https://rextester.com/IGYHZ78459

edit: Sphenic numbers trene OEIS luoon :V http://oeis.org/A007304

4 Likes
#13

3 thừa số đều phải nguyên tố và là 3 nguyên tố khác nhau, vì nếu không nguyên tố thì đã phân tích được thành 4

1 Like
#14

chạy thử code mới ra đúng rồi đóa :V

30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, 230, 231, 238, 246, 255, 258, 266, 273, 282, 285, 286, 290, 310, 318, 322, 345, 354, 357, 366, 370, 374, 385, 399, 402, 406, 410, 418, 426, 429, 430, 434, 435, 438, 442, 455, 465, 470, 474, 483, 494, 498,

thêm 1 dòng :smiling_face_with_three_hearts:

5 Likes
#15

yeppp, good job (y)
nhưng bạn lại giải luôn hộ chủ thớt rồi, haha =))

#16

Thiếu rồi anh ơi. :slight_smile:

8, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52, 63, 66, 68, 70, 75, 76, 78, 92,
98, 99, 102, 105, 110, 114, 116, 117, 124, 125, 130, 138, 147, 148, 153, 154, 164, 165, 170, 171,
172, 174, 175, 182, 186, 188, 190, 195, 207, 212, 222, 230, 231, 236, 238, 242, 244, 245, 246, 255,
258, 261, 266, 268, 273, 275, 279, 282, 284, 285, 286, 290, 292, 310, 316, 318, 322, 325, 332, 333,
338, 343, 345, 354, 356, 357, 363, 366, 369, 370, 374, 385, 387, 388, 399, 402, 404, 406, 410, 412,
418, 423, 425, 426, 428, 429, 430, 434, 435, 436, 438, 442, 452, 455, 465, 470, 474, 475, 477, 483,
494, 498

Thiếu mấy số nhỏ kìa. :slight_smile:

int sher(int n) {
    int count = 0;
    for (int a = n, i = 2; i * i <= a; i++)
        while (n % i == 0) {
            n /= i;
            if ((!n && count < 2) || ++count > 3) return 0;
        }
    return count + (n != 1) == 3;
}

Mất thêm 1 dòng. K có đưa được nốt thằng count vô for. :sob:

3 Likes
#17

3 thừa số khác nhau bạn :slight_smile: code bạn ko có xét khác nhau.

4 Likes
#20

(y)
à, tại n luôn dương rồi nên tôi mới để nó thành n>0
t hỏi vì thắc mắc tại sao phải kiểm tra điều kiện đó, vì có khi nào n = 0 được đâu.

#21

//bỏ qua việc xét đk 3 thừa số kahcs nhau
theo tôi nên thay dòng này thành

count++;
if (count >3) return false;
#22

Khác gì nhau. :confused:

Không đọc kỹ rồi. :cry:
Sửa lại thì không khác bài của a Nổ tẹo nào, thôi cứ để v. :kissing:

!n tương đương với n == 0 cơ a ơi. :slight_smile:
Nhưng viết v nó dài. :kissing:

3 Likes
#23

Đã sửa.

if(!n) khó hiểu vì nó là phủ định của phủ định :slight_smile: 0 là falsy, not false là true.

4 Likes
#24

if !n dễ hiểu mà, đọc là nếu ko có n :V hay n ko có giá trị, hay n = 0 :V

edit: có lẽ ở đây so sánh n == 0 dễ đọc hơn là !n vì n ko phải là 1 boolean :V

image
image.png845×292 35.1 KB

kinh thánh đã ghi rồi :V :V :V

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