Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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 CPP C++ 4.3.2 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

hide comments
2014-07-04 18:05:58 Black Hole
O(n*căn n) cuối cùng cũng AC :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.