好的,所以我喜欢使用SPOJ来练习编程和开发算法。我总是对问题有疑问。很多时候,当我的代码清楚地正确回答问题时,我会收到“错误答案”的消息。如果有人能告诉我是否有什么问题,或者为什么SPOJ会告诉我我的答案是错误的,那将是非常棒的!这是逐字逐句的问题:
素数发生器
彼得想为他的密码系统生成一些素数。帮助他!你的任务是生成两个给定数字之间的所有素数!
输入
输入以单行中的测试用例的
t
开头(t<=10
)。在下一个t
线中,有两个数字m
和n
(1 <= m <= n <= 1000000000, n-m<=100000
)被一个空格隔开。产量
对于每个测试用例打印所有素数
p
,使m <= p <= n
,每行一个数字,测试用空行分隔的情况。
我的代码:
int n;
scanf("%d", &n);
if(n > 10){ return 0; }
n = n*2;
int arr[n];
for(int i = 0; i < n; i++){ scanf("%d", &arr[i]); }
for(int i = 0; i < n; i += 2){
if(arr[i] >= 1 && arr[i] <= arr[i+1] && arr[i+1] <= 1000000000 && arr[i+1]-arr[i] <= 100000){
for(int j = arr[i]; j <= arr[i+1]; j++){
if(j % 2 == 1 || j == 2){
printf("%d\n", j);
}
}
printf("\n");
}
}
return 0;
INPUT:
2
7 11
2 9
OUTPUT:
7
9
11
2
3
5
7
9
很多时候,当我的代码清楚地正确回答问题时,我会收到“错误答案”的消息。
这不是其中之一,事实证明,尽管相反,你的代码似乎认为9
是一个素数。这条线:
if(j % 2 == 1 || j == 2)
结合您似乎正在打印所有奇数(和两个)的事实,表明您的主要检查不正确。
您可能应该从哪里开始使用简单的主要检查功能,例如:
int isPrime(int num) {
int chk = 2;
while (chk * chk <= num)
if ((num % chk) == 0)
return 0;
++chk;
}
return 1;
}
一旦你有它的工作,然后担心性能(我最喜欢的两个咒语是“错误是最不优化的状态”和“让它先工作,然后让它快速工作”)。
您可以查看优化的内容包括但不限于:
6n±1
形式的事实,有效地使isPrime
函数的速度增加三倍(参见here的解释)。对于第二个要点,您可以使用:
int isPrime(unsigned int num) {
// Special cases for 0-3.
if (num < 2) return 0;
if (num < 4) return 1;
int chk = 5, add = 2; // prime generator, 6n +/- 1.
while (chk * chk <= num) // check every candidate.
if ((num % chk) == 0) // check if composite.
return 0;
chk += add; // next candidate.
add = 6 - add; // alternate +2, +4.
}
return 1; // no factors, must be prime.
}