问题描述


已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式


输入一个正整数N。

输出格式

输出一个整数，表示你找到的最小公倍数。

样例输入

9

样例输出

504

数据规模与约定


1 <= N <= 106。

我语文不好，让大神解释，和说说解题算法，

相互互质  如何

$<=[106] of max:  1146390 = 106 * 105 * 103
$<=[105] of max:  1124760 = 105 * 104 * 103
$<=[104] of max:  1081912 = 104 * 103 * 101
$<=[103] of max:  1061106 = 103 * 102 * 101
$<=[102] of max:   999900 = 101 * 100 *  99
$<=[101] of max:   999900 = 101 * 100 *  99
$<=[100] of max:   960300 = 100 *  99 *  97
$<=[ 99] of max:   941094 =  99 *  98 *  97
$<=[ 98] of max:   903070 =  98 *  97 *  95
$<=[ 97] of max:   884640 =  97 *  96 *  95
$<=[ 96] of max:   830490 =  95 *  94 *  93
$<=[ 95] of max:   830490 =  95 *  94 *  93
$<=[ 94] of max:   795522 =  94 *  93 *  91
$<=[ 93] of max:   778596 =  93 *  92 *  91
$<=[ 92] of max:   745108 =  92 *  91 *  89
$<=[ 91] of max:   728910 =  91 *  90 *  89
$<=[ 90] of max:   681384 =  89 *  88 *  87
$<=[ 89] of max:   681384 =  89 *  88 *  87
$<=[ 88] of max:   650760 =  88 *  87 *  85
$<=[ 87] of max:   635970 =  87 *  86 *  85
$<=[ 86] of max:   606730 =  86 *  85 *  83
$<=[ 85] of max:   592620 =  85 *  84 *  83
$<=[ 84] of max:   551286 =  83 *  82 *  81
$<=[ 83] of max:   551286 =  83 *  82 *  81
$<=[ 82] of max:   524718 =  82 *  81 *  79
$<=[ 81] of max:   511920 =  81 *  80 *  79
$<=[ 80] of max:   486640 =  80 *  79 *  77
$<=[ 79] of max:   474474 =  79 *  78 *  77
$<=[ 78] of max:   438900 =  77 *  76 *  75
$<=[ 77] of max:   438900 =  77 *  76 *  75
$<=[ 76] of max:   416100 =  76 *  75 *  73
$<=[ 75] of max:   405150 =  75 *  74 *  73
$<=[ 74] of max:   383542 =  74 *  73 *  71
$<=[ 73] of max:   373176 =  73 *  72 *  71
$<=[ 72] of max:   342930 =  71 *  70 *  69
$<=[ 71] of max:   342930 =  71 *  70 *  69
$<=[ 70] of max:   323610 =  70 *  69 *  67
$<=[ 69] of max:   314364 =  69 *  68 *  67
$<=[ 68] of max:   296140 =  68 *  67 *  65
$<=[ 67] of max:   287430 =  67 *  66 *  65
$<=[ 66] of max:   262080 =  65 *  64 *  63
$<=[ 65] of max:   262080 =  65 *  64 *  63
$<=[ 64] of max:   245952 =  64 *  63 *  61
$<=[ 63] of max:   238266 =  63 *  62 *  61
$<=[ 62] of max:   223138 =  62 *  61 *  59
$<=[ 61] of max:   215940 =  61 *  60 *  59
$<=[ 60] of max:   195054 =  59 *  58 *  57
$<=[ 59] of max:   195054 =  59 *  58 *  57
$<=[ 58] of max:   181830 =  58 *  57 *  55
$<=[ 57] of max:   175560 =  57 *  56 *  55
$<=[ 56] of max:   163240 =  56 *  55 *  53
$<=[ 55] of max:   157410 =  55 *  54 *  53
$<=[ 54] of max:   140556 =  53 *  52 *  51
$<=[ 53] of max:   140556 =  53 *  52 *  51
$<=[ 52] of max:   129948 =  52 *  51 *  49
$<=[ 51] of max:   124950 =  51 *  50 *  49
$<=[ 50] of max:   115150 =  50 *  49 *  47
$<=[ 49] of max:   110544 =  49 *  48 *  47
$<=[ 48] of max:    97290 =  47 *  46 *  45
$<=[ 47] of max:    97290 =  47 *  46 *  45
$<=[ 46] of max:    89010 =  46 *  45 *  43
$<=[ 45] of max:    85140 =  45 *  44 *  43
$<=[ 44] of max:    77572 =  44 *  43 *  41
$<=[ 43] of max:    74046 =  43 *  42 *  41
$<=[ 42] of max:    63960 =  41 *  40 *  39
$<=[ 41] of max:    63960 =  41 *  40 *  39
$<=[ 40] of max:    57720 =  40 *  39 *  37
$<=[ 39] of max:    54834 =  39 *  38 *  37
$<=[ 38] of max:    49210 =  38 *  37 *  35
$<=[ 37] of max:    46620 =  37 *  36 *  35
$<=[ 36] of max:    39270 =  35 *  34 *  33
$<=[ 35] of max:    39270 =  35 *  34 *  33
$<=[ 34] of max:    34782 =  34 *  33 *  31
$<=[ 33] of max:    32736 =  33 *  32 *  31
$<=[ 32] of max:    28768 =  32 *  31 *  29
$<=[ 31] of max:    26970 =  31 *  30 *  29
$<=[ 30] of max:    21924 =  29 *  28 *  27
$<=[ 29] of max:    21924 =  29 *  28 *  27
$<=[ 28] of max:    18900 =  28 *  27 *  25
$<=[ 27] of max:    17550 =  27 *  26 *  25
$<=[ 26] of max:    14950 =  26 *  25 *  23
$<=[ 25] of max:    13800 =  25 *  24 *  23
$<=[ 24] of max:    10626 =  23 *  22 *  21
$<=[ 23] of max:    10626 =  23 *  22 *  21
$<=[ 22] of max:     8778 =  22 *  21 *  19
$<=[ 21] of max:     7980 =  21 *  20 *  19
$<=[ 20] of max:     6460 =  20 *  19 *  17
$<=[ 19] of max:     5814 =  19 *  18 *  17
$<=[ 18] of max:     4080 =  17 *  16 *  15
$<=[ 17] of max:     4080 =  17 *  16 *  15
$<=[ 16] of max:     3120 =  16 *  15 *  13
$<=[ 15] of max:     2730 =  15 *  14 *  13
$<=[ 14] of max:     2002 =  14 *  13 *  11
$<=[ 13] of max:     1716 =  13 *  12 *  11
$<=[ 12] of max:      990 =  11 *  10 *   9
$<=[ 11] of max:      990 =  11 *  10 *   9
$<=[ 10] of max:      630 =  10 *   9 *   7
$<=[  9] of max:      504 =   9 *   8 *   7
$<=[  8] of max:      280 =   8 *   7 *   5
$<=[  7] of max:      210 =   7 *   6 *   5
$<=[  6] of max:       90 =   6 *   5 *   3
$<=[  5] of max:       60 =   5 *   4 *   3