/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/bHcD
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
import flash.utils.Dictionary;
public class Test extends Sprite {
private var _tf : TextField;
public function Test() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
// _N = 2010;
// tr(comb(2, 3));
tr(solve(2010));
// tr(solve(60));
var g : int = getTimer();
tr((g - s) + " ms");
}
private var _maxis : Array;
private function solve(N : uint) : uint
{
_N = N;
_SQN = Math.sqrt(_N);
_primes = doEratosthenes(N);
_M = _primes.length;
_maxis = [];
var i : uint, j : uint, k : uint, l :uint;
for(i = 0;i < _M;i++){
if(_primes[i] * _primes[i + 1] > _N)break;
for(j = i + 1;j < _M;j++){
if(_primes[i] * _primes[j] <= _N){
if(comb(_primes[i], _primes[j]) > comb(_primes[i]) + comb(_primes[j])){
// _tf.appendText("" + [_primes[i], _primes[j]] + "\n");
_maxis.push({ns : [i, j], comb : comb(_primes[i], _primes[j])});
}
}else{
break;
}
}
}
for(i = 0;i < _M;i++){
if(_primes[i] * _primes[i + 1] * _primes[i + 2] > _N)break;
for(j = i + 1;j < _M;j++){
if(_primes[i] * _primes[j] * _primes[j + 1] > _N)break;
for(k = j + 1;k < _M;k++){
if(_primes[i] * _primes[j] * _primes[k] <= _N){
var c3 : uint = comb(_primes[i], _primes[j], _primes[k]);
if(c3 <= comb(_primes[i]) + comb(_primes[j]) + comb(_primes[k]))continue;
if(c3 <= comb(_primes[i], _primes[j]) + comb(_primes[k]))continue;
if(c3 <= comb(_primes[j], _primes[k]) + comb(_primes[i]))continue;
if(c3 <= comb(_primes[k], _primes[i]) + comb(_primes[j]))continue;
// _tf.appendText("" + [_primes[i], _primes[j], _primes[k]] + "\n");
_maxis.push({ns : [i, j, k], comb : c3});
}else{
break;
}
}
}
}
/*
for(i = 0;i < _M;i++){
if(_primes[i] * _primes[i + 1] * _primes[i + 2] * _primes[i + 3] > _N)break;
for(j = i + 1;j < _M;j++){
if(_primes[i] * _primes[j] * _primes[j + 1] * _primes[j + 2] > _N)break;
for(k = j + 1;k < _M;k++){
if(_primes[i] * _primes[j] * _primes[k] * _primes[k + 1] > _N)break;
for(l = k + 1;l < _M;l++){
if(_primes[i] * _primes[j] * _primes[k] * _primes[l] <= _N){
var c4 : uint = comb(_primes[i], _primes[j], _primes[k], _primes[l]);
var ij : uint = comb(_primes[i], _primes[j]);
var ik : uint = comb(_primes[i], _primes[k]);
var il : uint = comb(_primes[i], _primes[l]);
var jk : uint = comb(_primes[j], _primes[k]);
var jl : uint = comb(_primes[j], _primes[l]);
var kl : uint = comb(_primes[k], _primes[l]);
if(c4 <= comb(_primes[i]) + comb(_primes[j]) + comb(_primes[k]) + comb(_primes[l]))continue;
if(c4 <= ij + comb(_primes[k]) + comb(_primes[l]))continue;
if(c4 <= ij + comb(_primes[k], _primes[l]))continue;
if(c4 <= ik + comb(_primes[j]) + comb(_primes[l]))continue;
if(c4 <= ik + comb(_primes[j], _primes[l]))continue;
if(c4 <= il + comb(_primes[j]) + comb(_primes[k]))continue;
if(c4 <= il + comb(_primes[j], _primes[k]))continue;
if(c4 <= jk + comb(_primes[i]) + comb(_primes[l]))continue;
if(c4 <= jk + comb(_primes[i], _primes[l]))continue;
if(c4 <= jl + comb(_primes[i]) + comb(_primes[k]))continue;
if(c4 <= jl + comb(_primes[i], _primes[k]))continue;
if(c4 <= kl + comb(_primes[i]) + comb(_primes[j]))continue;
if(c4 <= kl + comb(_primes[i], _primes[j]))continue;
if(c4 <= comb(_primes[i], _primes[j], _primes[k]) + comb(_primes[l]))continue;
if(c4 <= comb(_primes[j], _primes[k], _primes[l]) + comb(_primes[i]))continue;
if(c4 <= comb(_primes[k], _primes[l], _primes[i]) + comb(_primes[j]))continue;
if(c4 <= comb(_primes[l], _primes[i], _primes[j]) + comb(_primes[k]))continue;
_tf.appendText("" + [_primes[i], _primes[j], _primes[k], _primes[l]] + "\n");
}else{
break;
}
}
}
}
}
*/
/*
for(i = 0;i < _maxis.length;i++){
tr(_maxis[i].ns.map(function(item:*, index:int, array:Array):uint {
return _primes[item];
}));
// tr(_maxis[i].comb);
}
*/
tr(_maxis.length);
var cts : Array = new Array(_M);
for(i = 0;i < _M;i++)cts[i] = 0;
for(i = 0;i < _maxis.length;i++){
if(_maxis[i].ns.length != 2)continue;
cts[_maxis[i].ns[0]]++;
cts[_maxis[i].ns[1]]++;
}
for(i = 0;i < _M;i++){
if(cts[i] != 0){
tr(_primes[i], cts[i]);
}
}
return 1234;
/*
_c = new Array(_maxis.length);
for(i = 0;i < _maxis.length;i++)_c[i] = {};
tr(_M);
tr(_maxis.length);
for(i = 0;i < _M && _primes[i] <= 499;i++);
_M = i + 1;
_used = new Array(_M);
for(i = 0;i < _M;i++)_used[i] = false;
return dfs(300) + 1;
*/
}
private var _c : Array;
private function dfs(pos : uint) : uint
{
var i : uint;
if(pos == _maxis.length){
var sum : uint = 0;
for(i = 0;i < _M;i++){
if(!_used[i]){
sum += comb(_primes[i]);
}
}
return sum;
}
/*
var mul : Number = 1;
for(i = 0;i < _M;i++){
if(_used[i] == true){
mul *= _primes[i];
}
}
if(_c[pos][mul])return _c[pos][mul];
*/
var ns : Array = _maxis[pos].ns;
var v : uint = dfs(pos + 1);
// _c[pos][mul] = v;
var n : uint;
for each(n in ns){
if(_used[n] == true){
// _c[pos][mul] = v;
return v;
}
}
for each(n in ns)_used[n] = true;
v = Math.max(v, dfs(pos + 1) + _maxis[pos].comb);
for each(n in ns)_used[n] = false;
// _c[pos][mul] = v;
return v;
}
private var _used : Array;
private var _primes : Array;
private var _M : uint;
private var _N : uint;
private var _SQN : uint;
// private var _cache : Array;
/*
private function dfs(pos : uint) : Object
{
if(pos == _M){
return {value : 0, comb : []};
}
if(_used[pos] == true)return dfs(pos + 1);
if(_primes[pos] > _SQN){
var cc : Array = [];
var sum : uint = 0;
for(var u : uint = pos;u < _M;u++){
if(_used[u] == true)continue;
cc.push([u]);
sum += _primes[u];
}
return {value : sum, comb : cc};
}
var max : uint = 0;
var maxc : Array;
var v : Object;
v = dfs(pos + 1);
v.value += comb(_primes[pos]);
max = v.value;
maxc = v.comb;
maxc.push([pos]);
var i : uint, j : uint, k : uint;
for(i = pos + 1;i < _M && _primes[pos] * _primes[i] <= _N;i++){
if(_used[i] == true)continue;
_used[i] = true;
v = dfs(pos + 1);
v.value += comb(_primes[pos], _primes[i]);
if(max < v.value){
max = v.value;
maxc = v.comb;
maxc.push([pos, i]);
}
for(j = i + 1;j < _M && _primes[pos] * _primes[i] * _primes[j] <= _N;j++){
if(_used[j] == true)continue;
_used[j] = true;
v = dfs(pos + 1);
v.value += comb(_primes[pos], _primes[i], _primes[j]);
if(max < v.value){
max = v.value;
maxc = v.comb;
maxc.push([pos, i, j]);
}
for(k = j + 1;k < _M && _primes[pos] * _primes[i] * _primes[j] * _primes[k] <= _N;k++){
if(_used[k] == true)continue;
_used[k] = true;
v = dfs(pos + 1);
v.value += comb(_primes[pos], _primes[i], _primes[j], _primes[k]);
if(max < v.value){
max = v.value;
maxc = v.comb;
maxc.push([pos, i, j, k]);
}
_used[k] = false;
}
_used[j] = false;
}
_used[i] = false;
}
var ret : Object = {value : max, comb : maxc};
return ret;
}
*/
private var _cache : Object = {};
private function comb(...elems) : uint
{
if(elems.length == 1 && _cache[elems[0]]){
return _cache[elems[0]];
}
var seed : Array = [1];
for each(var e : uint in elems){
var next : Array = [];
var i : uint, j : uint;
for each(var s : uint in seed){
for(j = e * s;j <= _N;j *= e){
next.push(j);
}
}
seed = next;
}
var max : uint = 0;
for each(s in seed){
if(max < s)max = s;
}
if(elems.length == 1){
_cache[elems[0]] = max;
}
return max;
}
private function doEratosthenes(n : int) : Array
{
var nn : uint = ((n / 2 - 1) >>> 5) + 1;
var ar : Vector.<uint> = new Vector.<uint>(nn);
var i : uint, j : uint;
for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
var sq : uint = (Math.sqrt(n) - 3) >>> 1;
for(var p : uint = 0;p <= sq;p++){
if(ar[p >>> 5] & (1 << (p & 31))){
var m : uint = (p << 1) + 3;
var m2 : uint = m << 1;
for(var mm : uint = m * m;mm <= n;mm += m2){
var ind : uint = (mm - 3) >>> 1;
ar[ind >>> 5] &= ~(1 << (ind & 31));
}
}
}
var ret : Array = [2];
for(i = 0;i < nn;i++){
for(j = 0;j <= 31;j++){
if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
}
}
return ret;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
}
}
