【算法】试除法求素数

心已赠人 2022-04-01 03:12 294阅读 0赞

判定一个数是否为素数(只能被1和本身整除)通常用小于这个数的所有数去试除他，看是否能被整除，显然不够简便。

##### 优化： #####

1.  除了2以外，其他偶数全都不为素数(能被2整除)，所以除了2以外只需要判断奇数是否为素数
2.  若要判断一个数n，不需要试除到n-1或者n/2，只需要到sqrt(n),  
    因为一个数若有因数，一个大于sqrt(n)一个小于sqrt(n)或者两者都为sqrt(n)
3.  一个数的独特因数一定为素数，可以将之前算出的素数保存，用于之后的判断

(1.3优化平级)

#### 代码实现(只给出了函数，未写主函数)： ####

优化：1.2  
**用于判断一个数是否为素数**

int isprime(int n)
    { 
    	int i = 0, end = sqrt(n);
    	if( n == 2)
    		return 1;
    	if(n % 2 == 0)
    		return 0;
    	for(i = 3; i <= end; i += 2)
    	{ 
    		if(n % i == 0)
    			return 0; 
    	}
    	return 1;
    }

优化：1.2.3  
**用于输出n以内的所有素数**  
需要在顺序遍历,将每个找到的素数存到数组内

int arr[max]={ 2,3,5};
    int func(int n)
    { 
        int j, m = 3, i = 2, end;
        for( ; ; )
        { 
            m += 2;              //2是素数，偶数都是非素数，奇数加2仍为奇数 
            end = sqrt(m);
            for(j = 1; arr[j] <= end; j++)
            { 
                if(m % arr[j] == 0)
                    break;
            }
            if(end < arr[j])
            { 
                arr[i++] = m;
            }
            if(fabs(m-n) <= 1)
                break;
        }
        for(j = 0; j < i ; j++)
        printf("%d ", arr[j]);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

相关试除法求约数

试除法求约数给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。输入格式第一行包含整数 n。接下来 n 行，每行包含一个

偏执的太偏执、/ 2024年03月31日 13:47/ 0 赞/ 72 阅读

相关试除法求约数：深入分析与实践

试除法求约数：深入分析与实践在数学和算法领域，约数，也称因数，是一个非常基础的概念。给定一个整数，它的所有约数是能够整除它的数。例如，6 的约数包括 1、2、3 和 6

矫情吗；*/ 2024年02月20日 08:50/ 0 赞/ 63 阅读

相关试除法求数的约数

上一篇博客：[分解质因数][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果

一时失言乱红尘/ 2022年11月18日 01:26/ 0 赞/ 185 阅读

相关求质数（素数）算法及其改进

质数概念：质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。数学还是要认真扣概念的，各

秒速五厘米/ 2022年09月27日 04:57/ 0 赞/ 191 阅读

相关求素数

求素数 Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述求小于n的所有素数的数量。输入

た入场券/ 2022年08月10日 04:58/ 0 赞/ 195 阅读

相关求素数算法（C语言）

以下是用C语言求一定范围内的素数。 include<stdio.h> include<math.h> int imax(int,int); v

秒速五厘米/ 2022年07月18日 05:55/ 0 赞/ 207 阅读

相关【算法】试除法求素数

判定一个数是否为素数(只能被1和本身整除)通常用小于这个数的所有数去试除他，看是否能被整除，显然不够简便。优化： 1. 除了2以外，其他偶数全都不为素数(能被2整除

心已赠人/ 2022年04月01日 03:12/ 0 赞/ 295 阅读

相关求素数

\include<stdio.h> \include<math.h> int prime(int m); int main(void) \{ int co

傷城~/ 2021年11月09日 23:46/ 0 赞/ 336 阅读

相关求素数

素数：在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。求0-n之间所有的素数。测试用例：20

╰+哭是因爲堅強的太久メ/ 2021年09月15日 05:02/ 0 赞/ 406 阅读

相关数论 - 质数(素数)基础【素数的判断 + 试除法分解质因数 + 求1-n之间的素数的三种筛法】

数论-质数基础 1.素数素数又称为质数，是指除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n,如果对任意的正整数a(1<a<n)，都有n%a

女爷i/ 2021年07月24日 18:57/ 0 赞/ 512 阅读