codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1076B.md (903B)


      1 Source: https://codeforces.com/problemset/problem/1076/B
      2 
      3 B. Divisor Subtraction
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an integer number $n$. The following algorithm is applied to it:
     22 
     23 1. if $n = 0$, then end algorithm;
     24 2. find the smallest prime divisor $d$ of $n$;
     25 3. subtract $d$ from $n$ and go to step $1$.
     26 
     27 Determine the number of subtrations the algorithm will make.
     28 
     29 Input
     30 
     31 The only line contains a single integer $n$ ($2 \le n \le 10^{10}$).
     32 
     33 Output
     34 
     35 Print a single integer — the number of subtractions the algorithm will make.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 1
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 4
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Note
     64 
     65 In the first example $5$ is the smallest prime divisor, thus it gets subtracted right away to make a $0$.
     66 
     67 In the second example $2$ is the smallest prime divisor at both steps.