1

我试图找到用户输入数字的最大素数。

到目前为止，我有：

#include <stdio.h>
#include <stdlib.h>

int main(void){
    int N;
    printf("Enter a positive number: ");
    scanf("%d", &N);
    int divisor = 1;

    for (int i = 2; i <= N; i++){
        if (N % i == 0){
            for (int j = 2; j < i; j++){
                if (i % j == 0 && j != i){
                    break;
                }
                else{
                divisor = i;
                }
            }
        }
    }
    printf("%i\n", divisor);
    return EXIT_SUCCESS;
}

但这似乎不起作用。我没有尝试不同的方法，而是试图首先了解为什么上述方法不起作用。

上面的代码应该通过首先检查数字 i 是否可以由用户输入的数字设计，然后检查 i 是否是素数，然后重复整个过程来查看是否存在更大的素数，来迭代所有可能的素数因子一个因素。但是它不起作用，因为它总是返回用户输入的数字 N，因为它有时会给出一个素数因子，大多数时候返回 N 或其他一些非素数。

4

7 回答 7

2 
for (int i = 2; i <= N; i++){ // outer loop
    if (N % i == 0){
        for (int j = 2; j < i; j++){ // inner loop
            if (i % j == 0 && j != i){
                break;
            }
            else{
            divisor = i;
            }
        }
    }
}

在外循环的最后一次迭代中i等于N。条件(N % i == 0)是true。我们处于内循环中。对于某些j情况(i % j == 0 && j != i)将是false. 我们在else条款中。所以，divisor = N。

于 2013-04-27T08:57:57.380 回答
2 
else {
    divisor = i;
}

情况不妙。您假设这会检查除数是否确实是素数，如果是素数，并且还除以输入数字，则将其分配给divisor变量。实际上，这不是发生的事情。相反，这将在遇到非素数时分配jto的当前值。你想要的是按升序检查数字的所有质因数，然后选择最后一个：divisorj

puts("Enter a positive integer:");
char buf[128];
fgets(buf, sizeof(buf), stdin);
unsigned n = strtoul(buf, NULL, 10);

unsigned d = 2, maxd = 1, orig = n;

while (d <= orig) {
    while (n % d == 0) {
        n /= d;
        maxd = d;
    }

    d++;
}

printf("\n\nMaximal prime factor: %u\n", maxd);
于 2013-04-27T09:00:01.247 回答
1 
for (int i = 2; i <= N; i++){
    if(N % i == 0){
        divisor = i;
        while((N/=i) % i == 0);
    }
}
于 2013-04-27T09:15:33.263 回答
0

我想内部循环需要一些小的修改

bool isPrimeDivisor = true;
for(int j=2; j<i;j++) {//inner loop
    if(i%j == 0 && j!=i) {
        isPrimeDivisor = false;
        break;
    }
}
if(isPrimeDivisor) divisor = i;
于 2013-04-27T09:08:10.783 回答
0

你试图找到你的数字的所有除数，直到数字本身。（它始终是自身的除数）。然后检查除数是否为素数，您尝试将所有数字的数字从 2 划分为 i-1。如果找到除数，则正确停止，但如果 j 不是除数，则说 i 是素数（并将其保存为最大除数）。

于 2013-04-27T09:02:17.133 回答
0

您可以使用循环向后工作，从 i = 小于或等于 N/2 的最大整数开始。检查 i 是否是一个因子，然后检查它是否是素数，如果是则返回它。

于 2014-02-09T22:35:06.603 回答
0 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//function to find factors
    long long int factors(long long a)
    {
        long long int i=1,c=0;
        for(i=1;i<=a;i++)
        {
            if(a%i==0)
            {
                c++;
            }
        }
        return c;
    }

    int main()
    { 
        long long int i,k,a,b;
        printf("enter an integer\n");
        scanf("%llu",&k);

        for(i=2;i<=k/2;i++)
        {                   
            if(k%i==0)
            {
                a=factors(i);
                if(a==2)                
                {
                    b=i;
                }   
            }
        }
    printf("\n______%.1llu_______\n",b);
    return 0;
}

这将为您提供整数的最大素数....

于 2017-04-23T01:15:03.583 回答