SAS 中的质因数分解循环

Question

我正在做一些小任务来提高我的编码和效率，我今天正在处理的问题来自项目 Euler，问题 3：

"Find the largest Prime of 600851475143"

我写的代码是：

data test;

a = 600851475143;
/*The subsequent a's are the next parts of the loop I'm trying to incorporate*/
/*a = 8462696833;*/
/*a = 10086647;*/
/*a = 6857;*/

if mod(a,2) = 0 then do;

a = a / 2;

end;

else do;

    do i = 3 to a until(flag);

        if mod(a,i) = 0 and i < a then do;

            b = i ;
            a = a / b ;
            flag = 1;
            output;

        end;
    end;

end;

run;

如何使变量成为一个循环并变小，然后在没有更多 a 时终止，即最后一次迭代不会产生数据集，因为没有因式分解。

我也很高兴收到有关如何使此代码更高效的任何提示，因为我正在努力学习

Answer 1

您将需要一些内循环来移除每个因子的所有幂。

因素检查的一些问题

去除 2 的幂仅去除因式分解中潜在的 2 的第一个幂。
do i 循环也是如此（实际上是 factor）。
do i 以 1 为单位进行迭代，这意味着您正在检查偶数。这不需要在删除 2 个因素后完成 - do i=3 to a by 2 … 会更好
- 一个数的质因数上限是sqrt(number)
- 如果你不想计算sqrt，你可以使用number/2
- 不管 to 是多少，当数字减少到 1 时你将退出因式分解循环，所以 to a 没问题。
- 更聪明的 'solver' 将跟踪动态已知素数并仅测试那些素数。如果在检查最后一个已知素数后没有实现完全分解，则必须前进 2

使用与其在解决方案中的角色相对应的变量名是有意义的——因此考虑使用 factor 而不是 i。当然对于个人代码，你可以使用你想要的名字，但是对于你或其他人将来维护的代码，最好的做法是好的变量名。

在 SAS 中，考虑处理（质因数分解）数据集中包含的任意数量的数字，而不是在 DTA 步骤的顶部对单个测试值进行硬编码。

SAS 中的循环是通过各种 do 代码结构完成的

do … while(condition); …iterated-statements… end;
- 0 个或更多循环 - 在执行任何迭代语句之前完成条件测试
do … until(condition); … end;
- 1 个或多个循环 - 条件测试在执行迭代语句后完成
do index=from-value to to-value by by-value; … end;
- index 以相等的步长变化，可以用作迭代语句的一部分
- to-value 计算一次，不能被迭代语句改变
- while 或 until 可以附加到 do index= 语句
- to-value 是可选的，但是会无限循环，除非存在 while 或 until，或者至少有一个迭代语句执行 leave 语句

你选择哪个取决于问题。

做一个数字数据集来处理

data numbers; input number; format number 16.; datalines;
64
720
30
600851475143
8462696833
10086647
6857
run;

示例代码

内循环用于去除多次出现的因素。

已更改：内循环 (= -1, 1) 用于将 6n+/-1 应用于 select 可能的因子。

data prime_factorizations(keep=number factor power);

  set numbers;
  objective = floor(abs(number));

  factor = 2;
  do power = 0 by 1 while (mod(objective,factor) = 0);
    objective = objective / factor;
  end;
  if power then output;

  factor = 3;
  do power = 0 by 1 while (mod(objective,factor) = 0);
    objective = objective / factor;
  end;
  if power then output;

  * after 2 and 3 all primes are of form 6n +/- 1;
  * however, not all 6n +/- 1 are prime;

  * in essence operate a sieve to check for factors;
  * of course the best sieve is a list of primes,
  * but 6n +/- 1 knocks out a lot of unnecessary checks; 

  do n = 1 to objective while (objective > 1);
    do offset = -1, 1;
      factor = 6*n + offset;
      do power = 0 by 1 while (mod(objective,factor) = 0);
        objective = objective / factor;
      end;
      if power then OUTPUT;
      if objective = 1 then leave;
    end;
  end;
run;

title "Prime factorization of some numbers";
proc print noobs data=prime_factorizations;
run;

proc sql;
  title "Max prime factor of various numbers";
  select number, max(factor) as max_prime_factor
  from prime_factorizations group by number;
quit;

title;

当然，这并不是真正的大质数搜索者的操作方式，但它是对使用任何给定语言进行编程的一个很好的介绍。回到 CS "survey of languages" 我会尝试用正在学习的新语言编写上面的代码。

SAS 中的质因数分解循环

Prime Factorisation Loop in SAS

loops

if-statement

sas

do-loops

sas-studio