Trial Multiplication for Factorization I am trying a trial multiplication for factorization. This is a general example, but each sequence can be specified to pairs of sequences \${p,q}\$ for a given \$n\$. For example, if \$n\$ ended in 3, then {\$p,q\$} would be: {1,3},{3,1},{7,9} and {9,7} with sequence steps of -10 and 10 respectively.

The essence of the method is if \$pq &lt; n\$, raise \$q\$. If \$pq &gt; n\$, lower \$p\$ while continuing where the last \$p\$ and the last \$q\$ left off.

#Trial Multiplication
TM&lt;- function (number){

    if (floor(sqrt(number))%%2==0)
    p_start &lt;&lt;- floor(sqrt(number))-1

    if (floor(sqrt(number))%%2&gt;0)  
    p_start &lt;&lt;- floor(sqrt(number))

    if (ceiling(sqrt(number))%%2==0)
    q_start &lt;&lt;- ceiling(sqrt(number))+1

    if (ceiling(sqrt(number))%%2&gt;0)  
    q_start &lt;&lt;- ceiling(sqrt(number)) 



    for (p in seq(p_start,1,-1)){   
      for (q in seq(q_start,number,1)){    

      #Quick primality tests for p and q... 
      #if(p%%3==0 | p%%5==0 | p%%7==0 | p%%11==0 | p%%13==0 | p%%17==0 | p%%19==0) break
      #if(q%%3==0 | q%%5==0 | q%%7==0 | q%%11==0 | q%%13==0 | q%%17==0 | q%%19==0) next 


      if(p*q==number)
      return(c(p,q)) 

      if(p*q&gt;number) break


      q_start&lt;&lt;- q
      p_start&lt;&lt;- p

      }


  #if(q%%3==0 | q%%5==0 | q%%7==0 | q%%11==0 | q%%13==0 | q%%17==0 | q%%19==0) break
  #if(p%%3==0 | p%%5==0 | p%%7==0 | p%%11==0 | p%%13==0 | p%%17==0 | p%%19==0) next 


  if(p*q==number)
  return(c(p,q))  

  if(p*q&lt;number) break

  p_start&lt;&lt;- p
  q_start&lt;&lt;- q

    }

}
What is slow is to create seq(q_start,number,1). Take the example where  number is 298,716,239: you are asking R to create a vector of nearly 300 million integers. It chokes. Instead of looping over sequences created in memory, it is easier to just keep the current value, increment and limit in memory. See for example:

TM &lt;- function (n) {

   n &lt;- as.integer(n)
   r &lt;- sqrt(n)
   p &lt;- as.integer(floor(r))
   q &lt;- as.integer(ceiling(r))

   while (p &gt;= 1L &amp; q &lt;= n) {
      if (p * q == n) return(c(p, q)) 
      if (p * q &gt; n) { p &lt;- p - 1L } else { q &lt;- q + 1L } 
   }
   stop("hmm... we should not be here...")
}

TM(1900)
TM(298716239)


Now that's a start... If you try with a large prime, e.g. 298716247, it will take a very long time to converge towards 1 * 298716247 though. So you will have to get more creative to make it converge faster. At least, you should be fixed about why your original code was so slow.



Edit: here is an idea I got for making it converge faster where you update both p and q at each iteration. I hope the math checks out and I did not leave a corner case:

TM2 &lt;- function (n){

   n &lt;- as.integer(n) # everything is faster with integers
   r &lt;- sqrt(n)
   p &lt;- as.integer(floor(r))
   q &lt;- as.integer(ceiling(r))
   while (p &gt;= 1L &amp; q &lt;= n) {
      if (p * q == n) return(c(p, q)) 
      if (p*q &gt; n) {
         p &lt;- p - 1L
         q &lt;- as.integer(floor(n / p))
      } else {
         q &lt;- q + 1L
         p &lt;- as.integer(ceiling(n / q))
      } 
   }
   stop("hmm...")
}

TM2(1900)
TM2(298716239)
TM2(298716247)