我可以使用两个循环来检查小于p素数的两个整数的所有组合,但效率非常低.有没有更好的算法来解决这个问题？任何的想法？
哪里p mod 4 = 1.
谢谢,
我一直在研究这个问题。
完整问题的链接http://acm.timus.ru/problem.aspx?num=1017&locale=en
我已经知道这是处理不同的分区和数论/背包问题。目标是有效地给出一个列表 n = [1,2,3,....n -1] 确定存在多少个加起来为 N 的无序集合。我说无序是因为给定的列表没有重复项，因此任何组合都可以排序为给定大小的有效特定答案以符合规则。我也理解一般概念是你从高度 1 开始并分支/添加所有可能的组合，直到新的高度超过砖块，并且仅当新高度用完所有剩余的砖块时才添加到总组合中那一点。我意识到有一些模式，就像您在进入 4 时已经知道 n = 3 存在多少个分区一样，因此使用该数据（动态编程）是解决方案的一部分。
我最终找到了以下解决方案。
n = int(input())
m = [[0 for i in range(n + 1)] for j in range(n + 1)]
m[0][0] = 1 # base case
for last in range(1, n + 1):
for left in range(0, n + 1):
m[last][left] = m[last - 1][left]
if left >= last:
m[last][left] += m[last - 1][left - …我已经实现了一个使用埃拉托斯特尼筛法算法列出素数的函数，如下所示：
func ListPrimes(n int) []int {
primeList := make([]int, 0)
primeBooleans := SieveOfEratosthenes(n)
for p := 0; p < n+1; p++ {
if primeBooleans[p] == true {
primeList = append(primeList, p)
}
}
return primeList
}
func SieveOfEratosthenes(n int) []bool {
primeBooleans := make([]bool, n+1)
sqrtN := math.Sqrt(float64(n))
for k := 2; k <= n; k++ {
primeBooleans[k] = true
}
for p := 2; float64(p) <= sqrtN; p++ {
if primeBooleans[p] == true {
primeBooleans = CrossOffMultiples(primeBooleans, p)
} …我已经看过过去的解决方案,但忘了哪里:是否有一个R函数将x = 1234变成其数字(1,2,3,4),反之亦然？
我目前正在尝试在MATLAB中编写一个程序来检查数字n是否为素数.对于初学者,我正在实施Fermat Primality Test.
费马指出,对于黄金p和1 <= b < p:
b^(p-1) = 1 (mod p)
所以在MATLAB中用p = 17,和b = 11
>> mod(b^(p-1),p)
要么
>> rem(b^(p-1),p)
我遇到的问题是MATLAB返回的实例0.但是,如果p是素数,它应该返回1.我看不出我错过了什么,所以非常感谢任何帮助!
什么是标尺函数的迭代实现？
该网站声称"标尺函数可以非递归地生成",但从未显示示例.
Python中的递归实现(来自同一网页)如下所示:
def ruler(k):
for i in range(1, k+1):
yield i
for x in ruler(i-1): yield x
我正在使用具有不同功能的数学软件中的一个,以找到给定区间内的所有Carmichael数字[a,b)
这是我的代码,但我不知道我是否已经正确地完成了它,因为我无法测试它,因为最小的Carmichael数字是560,这对我的电脑来说太大了.
#include <stdio.h>
int main() {
unsigned int begin, end;
printf("Write an int (begin):\n");
scanf("%d", &begin);
printf("Write an int (end):\n");
scanf("%d", &end);
int i;
for( int i=begin; i<end; i++ ) {
long unsigned int a_nr = i-1;
int a[a_nr];
for( int j=0; j<a_nr; j++ ) {
a[j] = j;
}
unsigned long c_nr[a_nr];
for( int k=0; k<a_nr; k++ ) {
unsigned long current_c_nr;
int mod;
for( int l=0; l<i; l++ ) {
current_c_nr= current_c_nr * a[k];
}
mod = …我想解决这个问题：
对于给定的序列 ，a[0], a[1], a[2],..., a[n-1]请找到该序列的“周期”。
周期是对于所有有效 i 满足 a[i] = a[i+k] 的最小整数 k (k >= 1)，并且 k 是 n 的除数。
我当前的解决方案是计算 n 的所有除数（这是 k）并测试所有 k，但这需要O(n * d(n)). 我认为这很慢。
有没有高效的算法？
有没有算法计算(b N mod p),给定a,b,p(这是一个素数)和(一个N mod p)但是N未知？
一个简单的方法是获得N的离散对数,但是有更有效的方法吗？或者问题相当于离散对数？
给定数字N,必须找到所有i的除数,其中i> = 1且i <= N. 无法理解.我是否需要使用素数分解？限制为N <= 10 ^ 9样本输出:
1 --> 1
2 --> 3
3 --> 5
4 --> 8
5 --> 10
6 --> 14
7 --> 16
8 --> 20
9 --> 23
10 --> 27
11 --> 29
12 --> 35
13 --> 37
14 --> 41
15 --> 45