在这个项目中,您将编写一个Java程序,从标准输入读取正整数n,然后打印出前n个素数.我们说如果存在整数k使得m = kd,即如果d均匀地划分为m,则整数m可被非零整数d整除.等价地,如果m(整数)除以d的余数为零,则m可被d整除.我们也会通过说d是m的除数来表达这一点.如果正整数p的唯一正除数为1且p为正整数p,则称为素数.该规则的一个例外是数字1本身,它被认为是非素数.非素数的正整数称为复合.欧几里德表明,有无数的素数.素数和复合序列开始如下:
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, …
有许多方法可以测试数字的素数,但最简单的方法就是简单地进行试验.首先将m除以2,如果它均匀分配,则m不是素数.否则,除以3,然后是4,然后是5,等等.如果在任何点发现m可以被2 dm-1范围内的数d整除,则停止,并得出结论m是复合的.否则,得出m是素数的结论.片刻的想法表明,人们不需要通过数字d进行任何试验划分,数字d本身是复合的.例如,如果试验除以2失败(即具有非零余数,因此m为奇数),则试验除以4,6或8或任何偶数也必须失败.因此,为了测试数字m的素数,只需要通过小于m的素数进行试验除法.此外,没有必要一直到m-1.人们只需要在下午2点范围内通过质数p进行m的试验分割.为了看到这一点,假设m> 1是复合的.然后存在正整数a和b,使得1 <a <m,1 <b <m,并且m = ab.但如果a> m和b> m,则ab> m,与m = ab相矛盾.因此,a或b中的一个必须小于或等于m.
要在java中实现此过程,您将编写一个名为isPrime()的函数,其函数具有以下签名:
static boolean isPrime(int m, int[] P)
根据m是素数还是复合函数,此函数将返回true或false.数组参数P将包含足够数量的素数来进行测试.具体来说,在调用isPrime()时,数组P必须包含(至少)2 pm范围内的所有素数p.例如,要测试m = 53的素数,必须按2,3,5和7进行连续的试验除法.自11> 53以来我们不再进一步.因此函数调用isPrime(53,P)的前提条件是P [0] = 2,P [1] = 3,P [2] = 5,P [3] = 7.在这种情况下返回值是真的,因为所有这些划分都失败了.与测试m = 143类似,必须通过2,3,5,7和11(从13> 143)进行试验分割.函数调用的前提条件是Preme(143,P)因此P [0] = …
可能重复:
找到少于200万的所有素数之和需要多长时间？
我试图在项目euler上实现一个简单的erathosthenes筛子来解决这个问题:
低于10的素数之和为2 + 3 + 5 + 7 = 17.
找出200万以下所有素数的总和.
我的代码仍然回答错误的答案 - 我一直得到142889228620项目euler不接受.
任何人都可以给我任何暗示为什么？这是代码:
import java.math.BigInteger;
public class Prime {
/*
* Input: an integer n > 1
*
* Let A be an array of bool values, indexed by integers 2 to n, initially
* all set to true.
*
* for i = 2, 3, 4, ..., while i^2 ? n: if A[i] is true: for j = i^2, i^2 +
* i, i^2 …我正在寻找一种算法,它可以帮助我分割数N,就像
N =(p 1 a)(p 2 b) .....*(p n z)
哪里
N is the given number
p is prime numbers smallest to greatest
a,b,..z are the power over the prime
* is the multiplication operation
我写了这段代码,它应该搜索素数并将它们放入数组中.这里是:
int[] prime_array = new int[(int)s.upper_bound];
int index_in_array = 0;
boolean are_we_done = false;
int index = 1;
boolean is_prime = true;
while (!are_we_done) {
try {
for (int i = 1; i < index; i++) {
if ((index%i)==0) {
is_prime = false;
}
}
if (is_prime) {
prime_array[index_in_array] = index;
index_in_array++;
}
index++;
is_prime = true;
}
catch (IndexOutOfBoundsException e) {
are_we_done = true;
break;
}
}
不幸的是,它捕获的唯一主要是1.任何想法为什么它不起作用？
我有这个我编写的python代码:
from math import *
limit = 100000
primes = [2]
for i in range(3, limit+1, 2):
is_prime = True
for j in range(3, floor(sqrt(i)), 2):
if i % j == 0:
is_prime = False
break
if is_prime: primes.append(i)
print(len(primes))
它说有9676个素数小于10万,当它应该是9592.如果我floor(sqrt(i))用公正替换它给出正确的答案i,但那时它非常慢.为什么我的算法不起作用？
我最近偶然发现了一个算法问题,我无法理解它.你得到一个正整数N <10 ^ 13,你需要选择一个非负整数M,这样得和:M N + N(N-1)/ 2的除数最小,介于1和N,包括在内.有人能指出我解决这个问题的正确方向吗？感谢您的时间.
我可以按照维基百科上列出的三元树算法生成所有互质对:https: //en.wikipedia.org/wiki/Coprime_integers
很快:
Start with two coprime branches: (2,1), (3,1), then iterate:
Branch 1: (2m-n,m)
Branch 2: (2m+n,m)
Branch 3: (m+2n,n)
然而,对于每对产生的空间使用的空间将增长三倍(并且说打印,或者不保留在存储器中).
这可能是haskell中的一个解决方案: 生成所有可能的coprimes的排序列表
但我正在寻找python中的东西,它没有懒惰的评估或无限的列表.
早上好,
我编写了以下代码,它与小数字一起使用,以找到数字的最大主要因素.我无法使用Prime,我需要提出一个手动解决方案.
def is_prime?(number)
list = (2..(Math.sqrt(number))).to_a
list.each do |i|
return false if number % i == 0
end
true
end
def biggest_prime(number)
list = (2..((number))).to_a
divisors = list.select{|i| is_prime?(i)}
divisors.select{|i| number % i == 0 }.max
end
13195的主要因素是5,7,13和29.
biggest_prime(13195) => 29
但是,当我尝试biggest_prime(600851475143)系统的边缘情况冻结.
任何人都可以告诉我如何重构我的代码,使其更有效率？
非常感谢!
我目前正在自学" Doask和Eijck 的Haskell逻辑,数学和编程之路 "一书,我在第3章.
在本章中,作者提供了一个Haskell代码,用于实现Sierat of Eratosthenes算法,我不喜欢它们的实现,所以我试着给出自己的实现; 但是,我的代码版本只删除2的倍数,我无法找出原因.这是代码:
sieve :: [Int] -> [Int]
sieve (0:xs) = sieve xs
sieve (x:xs) = x : sieve (mark x 2 xs)
where
mark :: Int -> Int -> [Int] -> [Int]
mark n k (y:ys)
| y == n*k = 0 : (mark n (k+1) ys)
| otherwise = y : (mark n (k) ys)
而输出是
*Ch3> sieve [2..]
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,...
那么,为什么代码不执行相同的删除操作的倍数,其他数字,如3,5,7 ..？