[Lý Thuyết Số - Toán Học]. Bài 100. Sàng phi hàm Euler
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho số nguyên dương N, liệt kê phi hàm euler của các số số từ 1 tới N và in ra màn hình.
Phi hàm euler của số X thể hiện số lượng số nguyên tố cùng nhau với X nằm trong khoảng từ [1, X].
Đầu vào
- Số nguyên N
Giới hạn
- 1≤N≤10^6
Đầu ra
- In ra phi hàm euler của các số từ 1 tới N
Ví dụ :
Input 01
15
Output 01
1 1 2 2 4 2 6 4 6 4 10 4 12 6 8
Bình luận
vector<int> phi(n + 1); for(int i = 0; i <= n; ++i) phi[i] = i; for(int i = 2; i <= n; ++i){ if(phi[i] == i){ for(int j = i; j <= n; j += i){ phi[j] -= phi[j] / i; } } } for(int i = 1; i <= n; i++) cout << phi[i] << " ";
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
:))))
Cười zì ấy b :v
mik k load đc ý của bạn nên hơi lú. Vậy đề này bịp đúng k bạn
Input với output hôm tui làm ấy, giờ ô ad update lại input với output rồi
Ùi dời ơi tốn nữa buổi giải bài này Công nhận khoai ác ra Giải bằng py thì bị quá thời gian miết
Code cho ae tham khảo và cmt trên có giải thích đấy
include <iostream>
include <vector>
using namespace std;
// Sàng Euler tính mảng phi[] cho 1 đến n // (phi[x] = số lượng số nguyên ≤ x nguyên tố cùng nhau với x) inline vector<int> computeTotients(int n) { vector<int> phi(n + 1); for (int i = 0; i <= n; ++i) { phi[i] = i; } for (int i = 2; i <= n; ++i) { if (phi[i] == i) { // i là số nguyên tố for (int j = i; j <= n; j += i) { phi[j] -= phi[j] / i; } } } return phi; }
int main() { ios::syncwithstdio(false); cin.tie(nullptr);
}