| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P148PROC - ROUND 8C - Dãy số EKG |
Chuỗi số nguyên dương EKG được sinh ra như sau: hai số đầu tiên là 1 và 2, các số tiếp theo là số nguyên dương nhỏ nhất chưa có trong dãy và có ước số chung với số đằng trước nó. Ví dụ các số đầu tiên của dãy số EKG sẽ là:
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27
Người ta chỉ ra được rằng tất cả các số nguyên dương đều sẽ xuất hiện trong dãy này. Và các số nguyên tố thì được xuất hiện theo thứ tự tăng dần. Bài toán đặt ra là: cho trước một số nguyên dương N, hãy cho biết số đó ở vị trí thứ bao nhiêu trong dãy EKG.
Input
Mỗi bộ test ghi trên một dòng số nguyên dương N (1<=N<=300000). Chú ý rằng đoạn dãy EKG chứa tất cả các số không quá 300000 thì sẽ không có số nào lớn hơn 1000000.
Input kết thúc khi N=0.
Output
Với mỗi bộ test, ghi ra màn hình dòng thông báo: “The number N appears in location P”
Trong đó P là vị trí của số N trong dãy.
Example
Input: 12
21
2
33
100000
299977
0 Output: The number 12 appears in location 7.
The number 21 appears in location 15.
The number 2 appears in location 2.
The number 33 appears in location 21.
The number 100000 appears in location 97110.
The number 299977 appears in location 584871.
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-23 |
| Thời gian chạy: | 3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
