筛选Eratosthenes - 素因子 [英] Sieve of Eratosthenes - prime factor

问题描述

我刚写了以下内容，利用筛子来找到大于2的自然数的最大素因子。

I just wrote the following to utilize the sieve to find the largest prime factor of some natural number greater than 2.

程序构建和运行，

我自己写的 - 并且相信它可能是非常低效的 - 在找到了什么筛是约。

I wrote this myself--and believe it will probably be extremely inefficient--after finding out what the sieve is about.

您能否提出改进建议？

谢谢。

//LARGEST PRIME FACTOR w/SIEVE OF ERATHOSTHENES
#include <iostream>
#include <math.h>

using namespace std;

unsigned long long int numberToCheck=0;

void sieve(unsigned long long int checkNumber)
{
    checkNumber=numberToCheck;
    unsigned long long int root=(int)(sqrt(checkNumber));
    unsigned long long int primeFlagger[checkNumber+1];

    for(unsigned long long int i=0;i<=checkNumber;i++)
    {
        primeFlagger[i]=1;
    }

    primeFlagger[0]=0;
    primeFlagger[1]=0;

    for(unsigned long long int j=2;j<=checkNumber;j++)
    {
        if(primeFlagger[j]==1)
        {
            for(unsigned long long int k=2;(k*j)<=checkNumber;k++)
            {
                primeFlagger[j*k]=0;
            }
        }
    }

    for(unsigned long long int l=checkNumber;l>=0;l--)
    {
        if(primeFlagger[l]==1)
        {
            if(checkNumber%l==0)
            {
                cout<<l<<" is the largest prime factor"<<endl;
                break;
            }
        }
    }
}

int main()
{
    cout<<"Largest prime factor less then or equal to? "<<endl;
    cin>>numberToCheck;
    cout<<endl;
    cout<<"Retrieving largest prime factor..."<<endl;

    sieve(numberToCheck);



    return 0;
}

推荐答案

c> unsigned long long int primeFlagger [checkNumber + 1]; 里面 sieve func太长。在全局范围中使用数组，在任何函数或动态内存分配之外。

Your array unsigned long long int primeFlagger[checkNumber+1]; inside sieve func is too long. Use array in global scope, outside of any function or dynamic memory allocation.

此外，您不需要 unsigned long long 。它是一个最大的整数数据类型，你只使用它的一个位。将类型更改为bool也会帮助您。

Also, you dont need unsigned long long. Its a largest integer data type and you use only one bit of it. Changing type to bool will help you too.

还有其他问题：

• unsigned long long int root =（int）（sqrt（checkNumber））; - 如果数字真的很大， sqrt（checkNumber）可以溢出 int ;


• unsigned long long int primeFlagger [checkNumber + 1]; - checkNumber 的类型可能大于 std :: size_t - 数组索引的类型并且大于可分配的最大存储器区域。


• checkNumber = numberToCheck; - 你不需要这个。 numberToCheck 其中已作为参数 checkNumber 传递到函数。 < code>< / c $ c> checkNummber将等于 numberToCheck ;


• for（unsigned long long int j = 2; j <= checkNumber; j ++） - 此循环应结束于 j <= root 。

• unsigned long long int root=(int)(sqrt(checkNumber)); - If number is really large, sqrt(checkNumber) can overflow int;
• unsigned long long int primeFlagger[checkNumber+1]; - type of checkNumber is probably larger than std::size_t - the type for array index and larger than largest memory area that can be allocated. You just cant make array size of unsigned long long.
• checkNumber=numberToCheck; - You dont need this. numberToCheck where already passed into function as parameter checkNumber. Inside sieve checkNummber will be equal to numberToCheck;
• for(unsigned long long int j=2;j<=checkNumber;j++) - this loop should ends then j<=root. This would be enough to mark all non-primal numbers.

如果你真的需要处理这么大的数字，使用分段筛。

If you really need to work with such large numbers, use segmented sieve.

这篇关于筛选Eratosthenes - 素因子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！