有关素数问题
问题描述：判断用户输入的整数是否为素数。
分析：素数是指只能被1和它本身整除的数。根据定义去测试：即用2、3、4…m-1依次去除m，若其中没有一个数能整除 m，则m为素数。
优化算法：用m依次除从2开始到该整数的1/2,
更优算法：用m依次除从2开始到该整数的平方根。
循环嵌套：打印输出100至200之间的全部素数。
k= int(sqrt(m));
for（i=2;i<=k;i++)
if(m%i==0) break;
if(i>=k) cout<<m<<“是素数\n”;
else cout<<m<<“不是素数\n”;
1、 任意输入一个整数判断是否为素数
#include <iostream.h>
#include <math.h>
bool is_prime(int n)
{    int i,j;
    for (i=2, j=int(sqrt(n)); i<=j; i++)
        if (n%i == 0)  return false;
    return true;
}
void main()
{    int n;
    cout << "请输入一个正整数：";
    cin >> n;          //从键盘输入一个正整数
    if (n < 2)
    {cout<<"您输入的数小于2。";
    return ;
    }
    if(n==2) cout<<2<<"是素数"<<endl;  //输出最小素数
    else if(is_prime(n))
            cout<<n<<"是素数"<<endl;
}
2、 函数应用举例：用函数实现求小于n的所有素数。
#include <iostream.h>
#include <math.h>
bool is_prime(int n)
{    int i,j;
    for (i=2, j=sqrt(n); i<=j; i++)
        if (n%i == 0) return false;
    return true;
}
void print_prime(int n, int count)
{    cout << n << ‘,’;
    if (count % 6 == 0) cout << endl;
}
void main()
{    int i,n,count=1;
    cout << "请输入一个正整数："
c++判断素数
    cin >> n;  //从键盘输入一个正整数
   
if (n < 2) return -1;
    cout << 2 << ",";  //输出第一个素数
    for (i=3; i<n; i+=2)
    {    if (is_prime(i))
        {    count++;
            print_prime(i,count);
        }
    }
    cout << endl;
}
3、
4、 歌德巴赫猜想
验证：2000以内的正偶数都能分解为两个素数之和（即验证歌德巴赫猜想对2000以内的正
偶数成立）。
问题分析与设计：
    为了验证歌德巴赫猜想对2000以内的正偶数成立，要将整数分解为两部分，然后判断分解出来的两个整数是否均为素数。若是，则满足题意；否则，重新进行分解和判断。
要求：写一个判断素数的函数。
#include <iostream.h>
#include <math.h>
bool is_prime(int i)
{    int j;
    if(i==1) return 0;
    if(i==2) return 1;
    if(!(i%2)) return 0;          //偶数返回0
    for (j=3; j<=int(sqrt(double(i))); j++)
        if (!(i%j)) return 0;
    return 1;
}
void main() 
{    int n,i;
    for(n=4;n<=2000;n+=2)        //可只测试1990……2000
    {  for(i=2;i<n;i++)
        {if(is_prime(i))
            if(is_prime(n-i))
            {cout<<n<<"="<<i<<"+"<<n-i<<endl;
            break;            //n到一组素数就输出并终止内循环
            }
        }
    }
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。