We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #234: Semidivisible numbers
  4. Discussions

Project Euler #234: Semidivisible numbers

Sort by

recency

|

23 Discussions

|

  • imDema
     + 0 comments

    I have implemented an efficient solution for the problem that can calculate the answer to the original euler project question (sum under 999966663333 answer not modular) however I'm struggling to compute the answer in the 10^18 range modulo 1004535809. The sieving I'm using is very efficient and the calculations are fast too, however sieving up to 10^9 will be pretty intensive even for the best sieves. Does anyone know about any resource on modular arithmetic that I could read to try and optimize the program by reducing the range using the module? Thanks

  • ronyv89
     + 0 comments

    Are there any edge cases here?

  • niteshcsehit
     + 0 comments

    this is my code in C#, I got just 8.22 can someone help.

    using System; using System.Collections.Generic; using System.IO; class Solution { static void Main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */ // int l = int.Parse(Console.ReadLine()); // int r = int.Parse(Console.ReadLine());

        string[] lr = Console.ReadLine().Split(' ');        
    long l = Convert.ToInt64(lr[0]);
    long r = Convert.ToInt64(lr[1]);
    long sum = 0;
    for (long number = l; number <= r; number++)
    {
        double lps = Math.Floor(Math.Sqrt(number));
        double ups = Math.Ceiling(Math.Sqrt(number));


        for (int i = 2; i < number / 2; i++)
        {
            if (i >= lps && lps > 2) { break; }
            if (lps % i == 0 && lps > 2)
            {
                lps--;
                i = 1;
            }
        }

        for (int i = 2; i < number / 2; i++)
        {
            if (i >= ups) { break; }
            if (ups % i == 0)
            {
                ups++;
                i = 1;
            }
        }

        if (number == (lps * lps)) { }
        else if (number % lps == 0 && number % ups == 0) { }
        else if (number % lps != 0 && number % ups != 0) { }
        else
        {
            sum = sum + number;
        }

    }

    Console.WriteLine(sum);
    Console.ReadLine();


}

    }

  • niteshcsehit
     + 0 comments

    how to convert string array value to long in c# as the given contraints say the limit of R will be 10^18.

  • ADARSHOFFICIAL11
     + 1 comment
    # Enter your code here. Read input from STDIN. Print output to STDOUT
import math as m
import sys

def lps(n):
    ref=m.floor(m.sqrt(n))
    result=1
    temp=[]

    for i in range(2,ref+1):
        #lets find out the greatest prime no less than ref
        
        for j in range(2,i):
            if i%j==0:
                break
        else:#this else is for FOR loop
            temp.append(i)
            #print("lps appended",temp)
    result=max(temp)
    return result # returns lps value for input as n

def ups(n):
    ref=m.ceil(m.sqrt(n))
    result=1
    temp=[]

    for i in range(ref,30):
        #lets find out the smallest prime no greater than ref
        for j in range(2,i):
            if i%j==0:
                break
        else:
            temp.append(i)
            #print("ups appended",temp)
    result=min(temp)
    return result

#main function:
arr=list(map(int,input().split()))
L=arr[0]
R=arr[1]
if (L not in range(4,pow(10,18))) or (R not in range(4,pow(10,18)))or((R-L)>pow(10,16)):
    sys.exit()

ans_lst=[]
try:
    for i in range(L,R+1):
        lps_val=lps(i)
        #print("debug lps val=",lps_val)
        ups_val=ups(i)
        #print("debug ups val=",ups_val)
        if (i%lps_val==0 and i%ups_val!=0) or (i%ups_val==0 and i%lps_val!=0):
            ans_lst.append(i)
    print(sum(ans_lst)%1004535809)
    #print("debug ans_list : ",ans_lst)
except ZeroDivisionError:
    print("Unexpected glitch")
    sys.exit()