[求助]判断一个数是不是质数！

wangmiaodi

UID: 2638
帖子: 74
积分: 170
在线时间: 7 小时

1^# wangmiaodi 发表于 2006-04-06 18:49

[求助]判断一个数是不是质数！

输入一个数：判断是不是质数
明天要交的作业。。
高手请帮忙。。。。谢谢　　　　　　

张自立

UID: 6223
帖子: 172
积分: 395
在线时间: 1 天 16 小时

2^# 张自立发表于 2006-04-06 19:29

我用语言描述下不一定对哦但是参考8错以下数字都为10进制
特例 N=0 N=1 N=2
首先范围为正奇整数（2进制中最后数字＝0的整数都是偶数）要用加法等
其他 N/K=Z 当k=2,3,4,5,.....|N/2|，
在K从1趋向N/2的过程中 Z的值的小数点第一位有输出立刻进行K＝n+1的算术
直到Z这个数的小数点后面没有东西输出时，且K=N的话，N就是质数拉　　　　　　

dearvoid

UID: 41384
帖子: 4
积分: 9
在线时间: 10 分钟

3^# dearvoid 发表于 2006-04-06 21:42

没什么难度，闲了的时候帮你想想

dearvoid

UID: 41384
帖子: 4
积分: 9
在线时间: 10 分钟

4^# dearvoid 发表于 2006-04-07 12:34

复制内容到剪贴板

代码:

[color=blue]-(user@host:tty)-(bash)-
[3711 0] $ [/color]cat prime_test.sh
#!/bin/bash
# vi:set ts=8 sw=4 et sta:
#
# Author: (dearvoid AT 263 DOT net)
#
# $Date: 2006-04-07 09:27:32 +0800 (Fri, 07 Apr 2006) $
# $HeadURL: svn://mac/repos/trunk/void/bash/prime_test.sh $
# $Revision: 77 $
#
#--------------------------------------------------------------------#

is_prime()
{
local n=$1

# not a valid integer, return false
[ "${n//[0-9]/}" ] && return 1

# 0, 1 are not prime
((n < 2)) && return 1

if ((n & 1)); then
      # odd
      local n_2=$((n >> 1))
      local i
      for ((i = 3; i < n_2; i += 2)); do
         ((n % i)) || return 1
      done

      return 0
else
      # even, only 2 is prime
      ((n > 2)) && return 1 || return 0
fi
}

#-- main() ----------------------------------------------------------#

{
N=200
echo "Prime numbers in [1, $N) :"
echo "------------------------------"
count=0
for ((n = 0; n < N; ++n)); do
      if is_prime $n; then
         printf "%8d" $n
         ((++count % 8)) || echo
      fi
done
((count % 8)) && echo
echo "------------------------------"
echo "Total: $count"
}
[color=blue]-(user@host:tty)-(bash)-
[3711 0] $ [/color]./prime_test.sh
Prime numbers in [1, 200) :
------------------------------
   2    3    5    7    11    13    17    19
   23    29    31    37    41    43    47    53
   59    61    67    71    73    79    83    89
   97    101    103    107    109    113    127    131
   137    139    149    151    157    163    167    173
   179    181    191    193    197    199
------------------------------
Total: 46
[color=blue]-(user@host:tty)-(bash)-
[3711 0] $ [/color]

dssn

UID: 3531
帖子: 125
积分: 287
在线时间: 21 小时

5^# dssn 发表于 2006-04-11 00:25

to dearvoid，没有那么复杂，还判断偶数，而且算法复杂度O(n)。判定到sqrt(n)即可。算法复杂度O(sqrt(n))从头到尾加合法性判定、空行，18行：

[HTML]
#!/usr/bin/perl -w
use strict;

my ($i,$n);

print "Input a number to test:";
chop($n=<STDIN>);

die "input must larger than 1" unless $n > 1;
die "input must be interger " unless $n == int($n);

for ($i=2; $i < int(sqrt($n)+1) ; $i++){
if (($n % $i) == 0) {
print "$n is not a prime number.\n";
exit(0);
}
}
print "$n is a prime number.\n"
[/HTML]　　　　　　

dssn

UID: 3531
帖子: 125
积分: 287
在线时间: 21 小时

6^# dssn 发表于 2006-04-11 01:08

原来是shell版，竟顺手写了perl脚本。改成shell函数应该也是类似。大概应该是这样的：
[CODE]
is_prime()
{
local n=$1

[ "${n//[0-9]/}" ] && return 1
((n < 2)) && return 1

local i
for ((i = 2; i*i < n+1; i ++)); do
((n % i)) || return 1
done
return 0
}
[/CODE]　　　　　　

dearvoid

UID: 41384
帖子: 4
积分: 9
在线时间: 10 分钟

7^# dearvoid 发表于 2006-04-11 09:16

仅为示例, 未敢言最优

俺的考虑: 少用乘除法, 多用加减法和位操作　　　　　　

alai

UID: 15268
帖子: 127
积分: 292
在线时间: 22 小时

8^# alai 发表于 2006-04-24 10:00

可以利用工具嘛

#!/bin/bash

n=`factor $1 | wc -w`
if [ $n -eq 2 ] ; then
echo $1 is prime.
fi　　　　　　

programfanny

UID: 32369
帖子: 34
积分: 78
在线时间: 1 小时

9^# programfanny 发表于 2006-05-02 21:14

prime(1..1000)　　　　　　