几个月来,我正在解决使用 java 的 euler 问题。很多时候堆大小限制了我,所以我想知道其他人在到达这个死胡同和令人沮丧的结局时会做什么。
一个很好的例子是问题“ http://projecteuler.net/problem=432 ”,我有一个简洁的函数可以在几毫秒内解决 10^6,但我不能将它应用于请求的值(10^ 11) 因为它需要一个大小为 10^11 的整数数组。
编辑:澄清问题。有什么方法可以筛选大数字吗?例如,如果你必须找到大于 10^10 的第一个素数,你会怎么做?
几个月来,我正在解决使用 java 的 euler 问题。很多时候堆大小限制了我,所以我想知道其他人在到达这个死胡同和令人沮丧的结局时会做什么。
一个很好的例子是问题“ http://projecteuler.net/problem=432 ”,我有一个简洁的函数可以在几毫秒内解决 10^6,但我不能将它应用于请求的值(10^ 11) 因为它需要一个大小为 10^11 的整数数组。
编辑:澄清问题。有什么方法可以筛选大数字吗?例如,如果你必须找到大于 10^10 的第一个素数,你会怎么做?
对于真正大的素数,您无法从 Eratosthenes 筛中获得,因为筛数组的最大长度受 Integer.MAX_VALUE 限制。
您可以通过最直接的方法计算它们 -
prime(N) = 如果 [0, sqrt(N)] 中的每个素数都不是 N 的素数。
并将您计算的所有大素数存储在一个或多个文件中。做一次,然后重复使用它们。当您处理需要大素数的欧拉问题时,首先将这些素数从文件加载到内存。
如果您的解决方案需要 10**11 个整数的数组,那么您需要购买一台内存至少为 745GB 的计算机。默认堆大小没有那么大似乎是合理的。或者你需要重新考虑它,而不是使用如此庞大的数组。