题目:判断一个数字是否为质数。

程序分析:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。

C语言实现:

#include<stdio.h>
#include<math.h>
#define MAX 1000
 
 
int prime[MAX];
 
int isPrimeNaive(int n)
{
    if(n <= 1)
        return 0;
    for(int i = 2; i < n; i++)
        if(n % i == 0)
            return 0;
    return 1;
}
 
int isPrime(int n)
{
    if(n<= 1)
        return 0;
    if(n == 2)
        return 1;
    if(n%2 == 0)
        return 0;
    int limit = (int)sqrt((double)n);
    for(int i = 3; i <= limit; i=i+2)
    {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
 
void sieve()
{
    prime[0] = 0;
    prime[1] = 0;
    for(int i = 2; i < MAX; i++)
        prime[i] = 1;
    int limit = (int)sqrt((double)MAX);
    for(int i = 2; i <= limit; i++)
    {
        if(prime[i])
            for(int j = i*i; j <= MAX; j+=i)
                prime[j] = 0;
    }
}
 
int isPrimeSieve(int n)
{
    if(prime[n])
        return 1;
    else
        return 0;
}
 
int main()
{
    sieve();
    printf("N=%d %d\n", 1, isPrime(1));
    printf("N=%d %d\n", 2, isPrime(2));
    printf("N=%d %d\n", 3, isPrime(3));
    printf("N=%d %d\n", 4, isPrime(4));
    printf("N=%d %d\n", 7, isPrime(7));
    printf("N=%d %d\n", 9, isPrime(9));
    printf("N=%d %d\n", 13, isPrime(13));
    printf("N=%d %d\n", 17, isPrime(17));
    printf("N=%d %d\n", 100, isPrime(100));
    printf("N=%d %d\n", 23, isPrime(23));
    printf("N=%d %d\n", 1, isPrime(1));
    return 0;
}

Java实现

package com.xxnotes;

/*
 * 题目:判断一个数字是否为质数
 */
import java.util.Scanner;

public class Cdemo33 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个整数\n");
        int a = scan.nextInt();
        int p = 0;
        for (int i = 2; i < a / 2; i++) {
            if (a % i == 0) {
                p = 0;
            }else {
                p = 1;
            }
        }
        if(p==1) {
            System.out.println(a+"是质数。");
        }else {
            System.out.println(a+"不是质数。");
        }
    }

}
最后编辑:2020年09月17日 ©著作权归作者所有

发表评论