性质判断

1) 性质判断：就是断定对象具有或不具有某种属性的判断 (也称为直言判断或直言命题)。 例如： 这个人是律师。

2) 性质判断的构成 

　Ｉ. 主项：表示被断定对象的概念，用 “S” 表示 

　Ⅱ. 谓项：表示被断定对象性质的概念，用 “P”表示 

　Ⅲ. 联项：也称联结项，它是联结主项和谓项的概念，它表示性质判断的“质”，分为肯定和否定两种。 一般用“是”和 “不是”表示。 

　Ⅳ. 量项： 表示所断定的主项的数量或范围的概念。量项又分为三种： 

　　a) 全称量项： 对主项的全部外延做了断定，所有的，凡、任何一个。 

　　b) 特称量项： 只对主项的部分外延做了断定。有些，有的。 

　　c) 单称量项： 所断定的主项只是某一个个别对象。这个、那个。 

3) 性质判断的分类： 根据性质判断质和量的划分，一共有六种类型。 

　Ｉ. 单称肯定判断：断定一个具体的对象具有某种性质的判断。逻辑形式：这个Ｓ是Ｐ，例如：中国是人口大国。 

　Ⅱ. 单称否定判断：断定一个具体的对象不具有某种性质的判断。逻辑形式：这个S不是P。例如：中国不是发达国家。 

　Ⅲ. 全称肯定判断： 断定一类对象都具有某种性质的判断。逻辑形式：所有S是P。例如：所有学生都是青年人。 

　Ⅳ. 全称否定判断： 断定一类对象中全体对象都不具有某种性质的判断。逻辑形式：所有S不是P。例如：所有学生都不是老年人。 

　Ⅴ. 特称肯定判断： 断定一类对象中有对象具有某种性质的判断。逻辑形式：有的S是P. 例如：有些学生是文科学生。 

　Ⅵ. 特称否定判断： 断定一类对象中有对象不具有某种性质的判断。

4) 量项“所有”、“有的”的替代表达形式 

　Ｉ. 与 “所有” 相似的表达：一切，任何，凡是，每一个，皆等。 

　Ⅱ. 与 “有的” 相似的表达：有些，许多，大多数、不少等。

5) 同一素材的判断：如果两个性质判断的主、谓项均相同，那么这两个判断就是同一素材的判断。例如： 

　Ｉ. 所有的产品都是合格的 

　Ⅱ. 所有的产品都不是不合格的。

6) 性质判断的对当关系： 

　Ｉ. 矛盾关系： 

　　ａ) 矛盾关系的特点： 必有一真，必有一假。 

　　b) 矛盾关系的本质：A与非A的关系 (A表示任何判断) 

　　c) 性质判断之间的矛盾关系： 

　　　“所有的Ｓ都是Ｐ” 与 “有的S不是P” 

　　　“所有的S都不是P” 与 “有的S是P” 

　　　“这个S是P” 与 “这个S不是P” 

　Ⅱ. 反对关系： 

　　ａ) 性质判断之间反对关系： 

    　　“所有的S都是P” 与 “所有的S都不是P” 

    　　“有的S不是P” 与 “有的S都是P” 

　　b) 反对关系的特点： 

　　　两个 “所有” 至少一假，可以同假。 

　　　两个 “有的” 至少一真，可以同真。

性质判断的变形推理

1) 换置推理：就是通过改变前提的质(肯定改为否定，否定改为肯定），从而得出结论的直接推理方法。 

例如：所有考生都是中国人，所以，所有考生都不是外国人。 

　Ｉ.  换置必须遵守的规则： 

　　① 主项和量项保持不变 

　　② 谓项变成其矛盾概念，亦”P”变为”非P”。 

　　③ 改变联项的性质，即肯定变否定；否定变肯定。 

　 

　Ⅱ. 换置推理的逻辑形式： 

　　① 所有S是P　换置得　所有Ｓ不是非Ｐ 

　　② 所有S不是P　换置得　所有Ｓ是非Ｐ 

　　③ 有的S是P　换置得　有的S是非P

2) 换位推理：就是交换前提中主谓项的位置，从而得出结论的直接推理。例如： 所有考生都不是外国人，所以，所有外国人都不是考生。 

　Ⅰ. 换位必须遵守的规则：不改变前提的质，只改变主谓项的位置 

　　① 所有S是P　可换位得　有的P是S 

　　② 所有S不是P　可换位得　所有P不是S 

　　③ 有的S是P　可换位得　有的P是S 

　　④ 有的S不是P　可换位得　有的P不是S 

　　 

　　

寄语


  
    船停在码头是最安全的，但那不是造船的目的；人待在家里是最舒适的，但那不是人生的追求。回首过往你会发现，最清晰的脚印，往往印在最泥泞的道路上。放松心态，努力前行，不辜负每一天。早安！
  
  
— 人民日报

本系列文章主要讲解 形式逻辑，系列文章总纲链接为：形式逻辑总纲

本章节思维导图如下所示（思维导图 迭代了以前的章节）：



1 性质判断

@1 性质判断的定义： 断定对象具有或不具有某种属性的判断，也称为直言判断或直言命题。 例如:所有 产品 是 合格的、有些 学生 不是 党员、这个 人 不是 盗贼。

@2 性质判断的构成：性质判断是由主项、谓项、联项和量项组成。上面案例可以总结如下：

量项
			
主项
			
联项
			
谓项
		
所有
			
产品
			
是
			
合格的
		
有些
			
学生
			
不是
			
党员
		
这个
			
人
			
不是
			
盗贼
		
主项:表示被断定对象的概念，用“S”表示。
	
谓项:表示被断定对象性质的概念，用“P”表示。
	
联项:它是联结主项和谓项的概念，分为肯定和否定两种。一般用“是”和“不是”表示。
	
量项:表示所断定的主项的数量或范围的概念。
量项分为三种：

全称量项：对主项的全部外延做了断定；常用的量词有：所有的、凡是、任何一个、每一个、皆。
	
特称量项：只对主项的部分外延做了断定；常用的量词有：有些、有的、许多、大多数、不少。（注意：特称量项“有些”、“有的”所表明的逻辑性质与现代汉语中的“有些”、“有的”的语法性质是有区别的。生活中的“有些”是指“仅仅有些”。如“我们班有些学生是 党员”，是指我们班仅仅有一部分学生是党员，而其他部分学生不是党员。而逻辑中的“有些” 是指“至少有些”。如“我们班有些学生是党员”，是指我们班至少有些同学是党员，其他 部分不清楚，具体指的是谁也不清楚，也有可能全部都是）
	
单称量项：所断定的主项只是某一个个别对象；常用的量词有：这个、那个。
@3 性质判断的分类 根据性质判断质和量的划分标准，一共有六种类型：

单称肯定：断定一个具体的对象具有某种性质的判断。 逻辑形式:这个S是P。例如:中国是人口大国。
	
单称否定：断定一个具体的对象不具有某种性质的判断。 逻辑形式:这个S 不是P。例如:中国不是发达国家。
	
全称肯定：断定一类对象中全体对象都具有某种性质的判断。 逻辑形式:所有S是P。例如:所有的学生都是青年人。
	
全称否定：断定一类对象中全体对象都不具有某种性质的判断。 逻辑形式:所有S不是P。例如:所有的学生都不是老年人。
	
特称肯定：断定一类对象中有对象具有某种性质的判断。 逻辑形式:有的S 是P。例如:有些学生是文科学生。
	
特称否定：断定一类对象中有对象不具有某种性质的判断。 逻辑形式:有的S不是P。例如:有的学生不是党员。
对应的逻辑方阵图如下所示（这个图要在理解的基础上记忆，最好是自己画几遍）：



逻辑方阵图的4种关系解读：

上反对关系（至少有1个命题为假，可能2个都是假）：所有S都是P，所有S都不是P。
	
下反对关系（至少有1个命题为真，可能2个都是真）：有的S是P，有的S不是P。
	
矛盾对应关系（一真一假）：所有S都是P 与 有的S不是P；所有S都不是P 与 有的S是P；这个S是P 与 这个S不是P。
	
从属关系：所有的S都是P→ 这个S是P→ 有的S是P；所有S都不是P→ 这个S不是P→ 有的S不是P
@4 案例分析：

1 “某理工大学的有些学生是北京人。” 这个判断的对象（主项）是什么?（分析：做一个逻辑转换得到-> 有些 某理工大学的学生 是 北京人，主项为 某理工大学的学生 ，因此答案为D）

A.某理工大学。B.某理工大学的有些学生。C.理工大学的学生。D.某理工大学的学生。E.学生。
2 并非所有老师都是青年人。下列哪项与上面的判断所表达的意思相同？（分析：所有老师都是青年人 与 有些老师不是青年人 为矛盾命题，因此可以推断出 有的老师不是青年人 为真，因此答案为C ）

A.所有老师都不是青年人。
	
B.没有一个老师不是青年人。
	
C.有的老师不是青年人。
	
D.老师中有青年人。
	
E.有的老师是青年人。
3 一家珠宝店珠宝被盗，经查可以肯定是甲、乙、丙丁四人中的某一个人所为。审讯中，他们各自说了一句话。

甲说:我不是罪犯。（逻辑转换：甲 非）
	
乙说:丁是罪犯。（逻辑转换：丁 是）
	
丙说:乙是罪犯。（逻辑转换：乙 是）
	
丁说:我不是罪犯。 （逻辑转换：丁 非）
经调查证实，四人中只有一个人说的是真话。根据以上条件，下列哪个判断为真？（分析：2 和4 矛盾，必有一真，因此1 3 假，即甲是罪犯，答案为A）

A.甲说的是假话，因此，甲是罪犯。
	
B.乙说的是真话，丁是罪犯。
	
C.丙说的是真话，乙是罪犯。
	
D.丁说的是假话，丁是罪犯。
	
E.四个人说的全是假话，丙才是罪犯。
4 小东在玩“勇士大战”游戏，进入第二关时，界面出现四个选项。

第一个选项是“选择任意选项都需支付游戏币”，（逻辑转换：任意选项 支付游戏币）
	
第二个选项是“选择本项后可以得到额外游戏奖励”，（逻辑转换：本项 额外奖励）
	
第三个 选项是“选择本项后游戏不会进行下去”，（逻辑转换：本项 游戏不再进行）
	
第四个选项是“选择某个选项不需要支付游戏币”。（逻辑转换：某个/有的选项 不支付游戏币）
如果四个选项中的陈述只有一句为真，则以下哪项一定为真?（分析：1和4互为矛盾命题，必有一真，2 和3为假，因此答案为E）

A.选择任意选项都需支付游戏币。
	
B.选择任意选项都无需支付游戏币。
	
C.选择任意选项都不能得到额外游戏奖励。
	
D.选择第二个选项后可以得到额外游戏奖励。
	
E.选择第三个选项后游戏能继续进行下去。
5 如果“我们班有的同学不会使用计算机（逻辑转换：有的S不是P）”是一个真判断，下面不能确定其真假是哪项?（分析：有的S不是P 为真，则 所有S是P 为假）

A.我们班至少有一个同学不会使用计算机。（逻辑转换：有的S不是P，与题干是一个意思，因此为真）
	
B.我们班所有同学都会使用计算机。（逻辑转换：所有S是P，与 有的S不是P  为 矛盾命题，因此为假）
	
C.我们班有的同学会使用计算机。（逻辑转换：有的S是P 与 有的S不是P 是下反对关系，必有一真，因此该命题无法判定）
	
D.不会使用计算机的有些是我们班的同学。（逻辑转换：有的[非P]是S 与 有的S是[非P] 满足互换原则，因此为真）
	
E.所有不会使用计算机的都不是我们班同学。（逻辑转换：所有[非P]不是S 与有的[非P]是S 为 矛盾关系，而有的[非P]是S 与 有的S是[非P] 满足互换原则，同真同假，因此该命题为假）
6 某公司财务部共有包括主任在内的 8 名职员。有关这 8 名职员，以下三个断定中，只有一个是真的：

有人是广东人。 （逻辑转换：有的人是 广东人）
	
有人不是广东人。（逻辑转换：有的人 不是 广东人）
	
主任不是广东人。 （逻辑转换：主任 不是 广东人）
以下哪项为真?（分析：1 和2 是下反对关系，至少有一真，所以3为假，即 主任是广东人，即 有的人是广东人为真，有的人 不是 广东人为假->所有人都是 广东人 为真，答案为A）

A.8 名职员都是广东人。
	
B.8 名职员都不是广东人。
	
C.只有一个不是广东人。
	
D.只有一个是广东人。
	
E.无法确定该部广东人的人数。
7 关于甲班体育达标测试，三位老师有如下预测: 

张老师说:“不会所有人都不及格。” （逻辑转换：不是 所有人都不及格->有的人会不及格）
	
李老师说:“有人会不及格。” （逻辑转换：有的人会不及格）
	
王老师说:“班长和学习委员都能及格。” （逻辑转换：有的人能及格）
如果三位老师中只有一人的预测正确，则以下哪项一定为真?（分析：1 和2 为下反对关系，必有一真，因此3为假。有的人能及格为假->所有人不及格为真，因此答案为A）

A.班长和学习委员都没及格。
	
B.班长和学习委员都及格了。
	
C.班长及格，但学习委员没及格。
	
D.班长没及格，但学习委员及格了。
	
E.以上各项都不一定为真。
8 所有的三星级饭店都被搜查过了（所有S都是P），没有发现犯罪嫌疑人的踪迹。 如果上述断定为真，则在下面四个断定中可确定为假的是:（分析：1 3为假，2 4 为真，因此答案为B）

没有三星级饭店被搜查过。（逻辑转换：不是所有S都是P，上反对关系，至少有一假，题干真 则该判断为假）
	
有的三星级饭店被搜查过。（逻辑转换：有的S是P 与 不是 所有S都是P 为 矛盾关系，因此为真）
	
有的三星级饭店没有被搜查过。 （逻辑转换：有的S不是P 与 所有S都是P 是矛盾关系，因此必为假）
	
犯罪嫌疑人躲藏的三星级饭店已被搜查过。（逻辑转换：因为所有的三星级饭店 都搜查过，因此该项为真）
A.仅I、II。B.仅I、III。C.仅II、III。D.仅I、III和IV。E.I、II、III和III。
9 北方人不都爱吃面食（有的 北方人不爱吃面食 为真 ->所有北方人爱吃面食 为假），但南方人都不爱吃面食（所有南方人都不爱吃面食 为假 -> 有的南方人爱吃面食 为真）。 如果已知上述第一个断定真，第二个断定假，则以下哪项据此不能确定真假? （分析：1为假，2 和3 命题无法判定，因此答案为D）

北方人都爱吃面食，有的南方人也爱吃面食，（逻辑转换说明：前 假，后真，命题确定为假）
	
有的北方人爱吃面食，有的南方人不爱吃面食 （逻辑转换：有的北方人爱吃面食 与 有的 北方人不爱吃面食 为下反对关系，其中至少有一真，前者确定为真，因此后者无法判定；有的南方人不爱吃面食 与 有的南方人爱吃面食 为下反对关系，至少有一真，后者为真，因此前者无法判定；因此命题无法判定真假）
	
北方人都不爱吃面食，南方人都爱吃面食（逻辑转换：所有北方人都不爱吃面食 与所有北方人爱吃面食 为上反对关系，至少有一假，而后者为假，因此前者无法判定；所有南方人都爱吃面食 与 所有南方人都不爱吃面食 为上反对关系，至少有一假，而后者为  假，因此前者无法判定；因此命题无法判定真假）
A.只有I。B.只有II。C.只有III。D.只有II和III。E.I、II和III。
10 有个叫艾克思的瑞典人最近发明了永动机。 如果上述断定为真，则以下哪项一定为真?（分析：这个S是P→ 有的S是P，因此答案为D）

A.由于永动机违反科学原理，上述断定不可能为真。
	
B.所有的瑞典人都没有发明永动机。
	
C.有的瑞典人没有发明永动机。
	
D.有的瑞典人发明了永动机。
	
E.发明永动机的只有瑞典人。
11 小李是四川人，他喜欢吃酸泡菜;小王也是四川人，她也喜欢吃酸泡菜;小陈是四川人，她也喜欢吃酸泡菜。我所认识的四川人都喜欢吃酸泡菜。 如果上述陈述为真，则可以得出下列哪项?（分析：有的四川人喜欢吃泡菜 但不能确定所有，因此答案为B）

A.所有四川人都喜欢吃酸泡菜。
	
B.有的四川人喜欢吃酸泡菜。
	
C.并非所有四川人都喜欢吃酸泡菜。
	
D.并非有的四川人喜欢吃酸泡菜。
	
E.有的喜欢吃泡菜的不是四川人。
2 性质判断的变形推理

@1 换质推理（简单来说就是双重否定，是P<=>不是非P）：通过改变前提的质(肯定改为否定，否定改为肯定)，从而得出结论的直接推理方法。例如: 所有考生都是中国人-> 所有考生都不是外国人。

@2 换位推理：通过交换前提中主、谓项的位置(主项变谓项，谓项变主项)，从而得出结论的直 接推理。例如: 所有考生都不是外国人， 所以，所有外国人都不是考生。 换位必须遵守的规则: 不改变前提的质，只改变主项 和 谓项的位置。

所有S是P 可换位得: 有的P是S
	
所有S不是P 可换位得: 所有P不是S
	
有的S是P 可换位得: 有的P是S
	
有的S不是P 不能换位得: 有的P不是S
@3 逻辑方阵图重新构建后如下所示（添加 换位推理，因为 是P<=>不是非P 相对较为容易，因此不在图上予以体现）：



增添内容 说明如下（这里采用 红绿黄 三色灯，方便记忆和理解）：

所有S是P 可换位得: 有的P是S（双层空心圆，局部置换）
	
所有S不是P 可换位得: 所有P不是S（空心圆，直接置换）
	
有的S是P 可换位得: 有的P是S（空心圆，直接置换）
	
有的S不是P 不能换位得: 有的P不是S（实心圆，不可置换）
@4 案例分析

1 已知“有些鸟不会飞”，据此可得?（有些S是P <=>有些P是S，因此答案是E，注意不是A）

A.有些会飞的不是鸟。B.所有鸟会飞。C.所有会飞的不是鸟。D.所有不会飞的是鸟。E.有些不会飞的是鸟。
2 从“这个班上所有学生都是学会计的”可推出以下结论，除了?（分析： ABCD均为真，E为假）

A.有学会计的是这个班上的学生。（逻辑转换：所有S都是P，推断得到：有的P是S，命题为真）
	
B.并非这个班上有的学生不是学会计的。（逻辑转换：这个班上有学生不是学会计的 与 这个班上所有学生都是学会计的 是矛盾 关系，后者为真，前者必为假，则前者的否命题为真）
	
C.这个班上有学生是学会计的。（逻辑转换：这个S是P→ 有的S是P，命题为真）
	
D.并非这个班上所有学生都不是学会计的。（逻辑转换：这个班上所有学生都不是学会计的 与 这个班上所有学生都是学会计的 是上反对 关系，至少有一个为假，后者为真，前者必为假，则前者的否命题为真）
	
E. 有学会计的不是这个班上的学生。（与A选项互为矛盾关系，A真，则E假）
3 有些便宜货不是假货，因此，有些假货不是便宜货。以下哪项最能说明上述推理不成立? （分析：相对来说最类似的推理模式是B选项：有些S不是P ->有些P不是S，因此答案为B）

A.有些便宜货不是好货，因此，有些便宜货是好货。（不类似的错误推理模式：有些S不是P ->有些S是P）
	
B.有些人不是坏人，因此，有些坏人不是人。（最类似的错误推理模式：有些S不是P ->有些P不是S）
	
C.所有商品都是有价值的，因此，所有有价值的都是商品。（不类似的错误推理模式：所有S是P ->所有P是S）
	
D.有些发明家是自学成才的，因此，有些自学成才者是发明家。（不类似的正确推理模式：有些S是P ->有些P是S）
	
E.没有宗教是科学，因此，没有科学是宗教。（不类似的正确推理模式：所有S是P ->所有P是S）
4 凡美的都是真的，凡真的都是不容怀疑的，而美的事物是存在的。 根据上述陈述可以推出下列哪项?（分析： ABDE均为 错误推断/无法推断，正确答案为C）

A.凡真的都是美的。（错误推理：所有S是P ->所有P是S）
	
B.有的美的值得怀疑。（逻辑转换：凡美的都是真的，凡真的都是不容怀疑的 推断出 凡美的都是不容怀疑的）
	
C.有的真的是美的。（正确推理：所有S是P ->有的P是S）
	
D.凡不美的都是要怀疑的。（错误推理：所有S是P ->所有非P是非S）
	
E.凡是真的都是存在的。（无法推断）

 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

 

分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。

分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。

 

//素数判断
int isPrime(u32 n) {
    for (u32 i = 2; i < n; i++) {
        //可以被别的数整除，不是素数
        if (n % i == 0)
            return 0;
    }
    return 1;
}
//质因数分解
int getPrimeFactor(u32 n) {    //可以不返回值，此处返回-1表示出错，返回1表示正常。
    //1以下的整数都不是素数
    if (n < 2)
        return -1;
    //判断是否是素数,如果是直接输出
    if (isPrime(n)) {
        printf("%d\t", n);
        return 1;
    }
    else {
        //递归因式分解
        for (u32 i = 2; i < n; i++) {
            if (n % i == 0) {
                printf("%d\t", i);
                getPrimeFactor(n / i);
                break;
            }
        }
    }
    return 1;
}

int main(void)
{
    int a = 1000;
    getPrimeFactor(a); //分机质因数
    getchar();
    return 0;
}


输出结果是：2 2 2 5 5


 

前言
之前就想写一篇关于分解质因数的文章，原因也是九度oj上有几道跟质因数分解有关的题目没有思路，这次找完工作学java的同时进行一些查缺补漏




原理&&方法
把一个合数分解为若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数，分解质因数只针对合数


求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式：


以24为例：


2 -- 24


2 -- 12


2 -- 6


3 （3是质数，结束）


得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3




代码
可先用素数筛选法，筛选出符合条件的质因数，然后for循环遍历即可，通过一道题目来show一下这部分代码


题目
题目描述：
求正整数N(N>1)的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入：
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出：
对于每组数据，输出N的质因数的个数。
样例输入：
120
样例输出：
5
提示：
注意：1不是N的质因数；若N为质数，N是N的质因数。

ac代码

#include <stdio.h>

int main()
{
	int n, count, i;

	while (scanf("%d", &n) != EOF) {
		count = 0;

		for (i = 2; i * i <= n; i ++) {
			if(n % i == 0) {
				while (n % i == 0) {
					count ++;
					n /= i;
				}
			}
		}

		if (n  > 1) {
			count ++;
		}

		printf("%d\n", count);
	}

	return 0;
}



深入理解
我所谓的深入理解，就是通过4星的题目来灵活运用分解质因数的方法，题目如下


题目
题目描述：
给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
输入：
两个整数n(2<=n<=1000)，a(2<=a<=1000)
输出：
一个整数.
样例输入：
6 10
样例输出：
1



思路
a^k和n!都可能非常大，甚至超过long long int的表示范围，所以也就不能直接用取余操作判断它们之间是否存在整除关系，因此我们需要换一种思路，从分解质因数入手，假设两个数a和b：


a = p1^e1 * p2^e2 * ... * pn^en,  b = p1^d1 * p2^d2 * ... * pn^dn, 则b除以a可以表示为：


b / a = (p1^d1 * p2^d2 * ... * pn^dn) / (p1^e1 * p2^e2 * ... * pn^en)


若b能被a整除，则 b / a必为整数，且两个素数必护质，则我们可以得出如下规律：

若a存在质因数px，则b必也存在该质因数，且该素因数在b中对应的幂指数必不小于在a中的幂指数


另b = n!, a^k = p1^ke1 * p2^ke2 * ... * pn^ken，因此我们需要确定最大的非负整数k即可。要求得该k，我们只需要依次测试a中每一个素因数，确定b中该素因数是a中该素因数的幂指数的多少倍即可，所有倍数中最小的那个即为我们要求得的k


分析到这里，剩下的工作似乎只是对a和n!分解质因数，但是将n!计算出来再分解质因数，这样n!数值太大。考虑n!中含有素因数p的个数，即确定素因数p对应的幂指数。我们知道n!包含了从1到n区间所有整数的乘积， 这些乘积中每一个p的倍数（包括其本身）都对n!贡献至少一个p因子，且我们知道在1到n中p的倍数共有n/p个。同理，计算p^2，p^3,...即可


代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 1001
 
int prime[N], size;
 
/** 
 * 素数筛选法进行预处理
 */
void initProcess()
{
    int i, j;
     
    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {
        prime[i] = 1;
    }
 
    size = 0;
 
    for (i = 2; i < N; i ++) {
        if (prime[i]) {
            size ++;
            for (j = 2 * i; j < N; j += i) {
                prime[j] = 0;
            }
        }
    }
}
 
int main(void)
{
    int i, n, a, k, num, count, base, tmp, *ansbase, *ansnum;
     
    // 预处理
    initProcess();
 
    while (scanf("%d %d", &n, &a) != EOF) {
        ansbase = (int *)calloc(size, sizeof(int));
        ansnum = (int *)calloc(size, sizeof(int));
 
        // 将a分解质因数
        for (i = 2, num = 0; i < N && a != 1; i ++) {
            if (prime[i] && a % i == 0) {
                ansbase[num] = i;
                ansnum[num] = 0;
                 
                while (a != 1 && a % i == 0) {
                    ansnum[num] += 1;
                    a = a / i;
                }
 
                num ++;
            }
        }
 
        // 求最小的k
        for (i = 0, k = 0x7fffffff; i < num; i ++) {
            base = ansbase[i];
            count = 0;
            while (base <= n) {
                count += n / base;
                base *= ansbase[i];
            }
 
            tmp = count / ansnum[i];
            if (tmp < k) k = tmp;
        }
 
        printf("%d\n", k);  
    }
 
    return 0;
}
 
/**************************************************************
    Problem: 1104
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:916 kb
****************************************************************/



约数个数定理

对于一个大于1的正整数n可以分解质因数：n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an, 则n的正约数的个数为：(a1 + 1) * (a2 + 1) * ... *(an + 1).其中p1,p2,..pn都是n的质因数，a1, a2...an是p1,p2,..pn的指数


证明
n可以分解质因数：n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,


由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 ，共（a1+1）个;同理p2^a2的约数有（a2+1）个......pk^ak的约数有（ak+1）个


故根据乘法原理：n的约数的个数就是(a1+1）*（a2+1）*（a3+1）*…* (ak+1)



题目
题目描述：
输入n个整数,依次输出每个数的约数的个数
输入：
输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出：
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
样例输入：
5
1 3 4 6 12
样例输出：
1
2
3
4
6

代码

#include <stdio.h>
#include <stdlib.h>
 
#define N 40000
 
typedef long long int lint;
 
int prime[N], size;
 
void init()
{
    int i, j;
 
    for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) {
        prime[i] = 1;
    }
     
    size = 0;
 
    for (i = 2; i < N; i ++) {
        if (prime[i]) {
            size ++;
            for (j = 2 * i; j < N; j += i)
                prime[j] = 0;
        }
    }
}
 
lint numPrime(int n)
{
    int i, num, *ansnum, *ansprime;
    lint count;
 
    ansnum = (int *)malloc(sizeof(int) * (size + 1));
    ansprime = (int *)malloc(sizeof(int) * (size + 1));
 
    for (i = 2, num = 0; i < N && n != 1; i ++) {
        if (prime[i] && n % i == 0) {
            ansprime[num] = i;
            ansnum[num] = 0;
            while (n != 1 && n % i == 0) {
                ansnum[num] += 1;
                n /= i;
            }
            num ++;
        }
    }
 
    if (n != 1) {
        ansprime[num] = n;
        ansnum[num] = 1;
        num ++;
    }
 
    for (i = 0, count = 1; i < num; i ++) {
        count *= (ansnum[i] + 1);
    }
 
    free(ansnum);
    free(ansprime);
 
    return count;
}
 
 
int main(void)
{
    int i, n, *arr;
    lint count;
 
    init();
 
    while (scanf("%d", &n) != EOF && n != 0) {
        arr = (int *)malloc(sizeof(int) * n);
        for (i = 0; i < n; i ++) {
            scanf("%d", arr + i);
        }
 
        for (i = 0; i < n; i ++) {
            count = numPrime(arr[i]);
            printf("%lld\n", count);
        }
 
        free(arr);
    }
 
    return 0;
}
/**************************************************************
    Problem: 1087
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:190 ms
    Memory:1068 kb
****************************************************************/