求<=n的所有素数

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

int main(int argc, char **argv)
{
    if (argc != 2) {
        printf("Usage: ./a.out <num>\n");
        exit(EXIT_FAILURE);
    }

    int n = atoi(argv[1]);
    int arr[n + 1];

    // init
    int i;
    for (i = 0; i <= n; i++)
        arr[i] = i;

    int p;
    for (p = 2; p < n; p++)
        for ( i = p + 1; i <= n; i++)
            if (i % p == 0)
                arr[i] = 0;

    // display all prime number
    for (i = 0; i <= n; i++)
        if (arr[i] != 0)
            printf("%d\n", arr[i]);

    exit(EXIT_SUCCESS);
}

评论

2 楼 steven-zhou 2008-10-30  

谢谢superloafer的提醒:)
我把算法优化了下，详见下:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <math.h>

#define IS_PRIME    1

int main(int argc, char **argv)
{
    if (argc != 2) {
        printf("Usage: ./a.out <num>\n");
        exit(EXIT_FAILURE);
    }

    int n = atoi(argv[1]);
    int primes[n + 1];
    int rsqrt = (int)sqrt(n) + 1;
    int i;
    int p;

    // init
    memset(primes, 0, sizeof(primes));
    primes[2] = IS_PRIME;

    for (i = 3; i <= n; i += 2)
        primes[i] = IS_PRIME;

    for (p = 3; p <= rsqrt; p += 2)
        for ( i = p + 2; i <= n; i += 2) {
            if (!primes[i])
                continue;
            primes[i] = i % p;
        }

    // display all prime numbers
    for (i = 0; i <= n; i++)
        if (primes[i])
            printf("%d\n", primes[i]);

    exit(EXIT_SUCCESS);
}

1 楼 superloafer 2008-10-30  

你这个程序好像有点问题哦。
1.程序会把1作为质数输出（根据质数定义，1显然不是质数）
2.效率比较低哦，一般的算法书都有更好的解法。

import java.util.*;

public class MathTest 
{
	public static void main(String[] args) 
	{
		if(args.length < 1) {
			return;
		}

		int k = Integer.parseInt(args[0]);

		if(k <= 0) {
			return;
		}
		
		boolean isPrime;
		List<Integer> primeList = new ArrayList<Integer>();
		for(int i = 2; i <= k; i++) {
			isPrime = true;
			for(int j = 2; j <= (int)Math.sqrt(i); j++) {
				if( i % j == 0) {
					isPrime = false;
					break;
				}
			}

			if(isPrime) {
				primeList.add(i);
			}
		}
	}
}